Bài 1. Mua laptop
Xem dưới dạng PDFNăm nay, dịch covid-19 diễn ra khá phức tạp ở nước ta, nhiều trường học các em học sinh không được đến trường. Trong tình hình ấy, Bộ Giáo Dục đã định hướng việc học và dạy học trực tuyến trên cả nước áp dụng cho các tỉnh thành thuộc vùng đỏ. Do nhu cầu học trực tuyến của các em học sinh dẫn đến giá thành của các máy tính xách tay (laptop) tăng phi mã, gây khó khăn rất nhiều cho các bậc phụ huynh khi muốn mua một chiếc laptop cho con em mình.
Bác phụ huynh XYZ muốn mua cho con mình một chiếc laptop, bác tham khảo ý kiến của một số các chuyên gia về máy tính và được những câu trả lời như sau:
- Chuyên gia thứ nhất: máy tính \(i\) tốt hơn máy tính \(j\) khi giá thành của máy tính \(i\) cao hơn máy tính \(j\).
- Chuyên gia thứ hai: máy tính \(i\) tốt hơn máy tính \(j\) khi hiệu suất của máy tính \(j\) cao hơn máy tính \(j\).
- Chuyên gia thứ ba: máy tính \(i\) tốt hơn máy tính \(j\) khi mà giá của máy tính \(i\) thấp hơn máy tính \(j\) nhưng hiệu suất của máy tính \(i\) lại cao hơn máy tín \(j\).
Cho rằng ý kiến của chuyên gia thứ ba là hợp lý, phụ huynh XYZ quyết định sẽ tìm mua chiếc laptop như ý kiến của chuyên gia này.
Bác hỏi \(n\) cửa hàng bán máy tính, cửa hàng thứ \(i\) tư vấn nên mua máy tính có giá là \(a[i]\) và hiệu suất là \(b[i]\).
👉 Yêu cầu: Hãy cho biết, bác phụ huynh XYZ có thể có bao nhiêu lựa chọn cho việc mua máy tính của mình (dựa trên ý kiến tham khảo của chuyên gia thứ ba).
Input: LAPTOP.INP
- Dòng 1: chứa số nguyên dương \(n\) \((1 ≤ n \le10^5)\) – số lượng cửa hàng máy tính.
- \(n\) dòng tiếp theo: dòng thứ \(i\) chứa hai số nguyên dương là \(a[i], b[i] (1≤a[i], b[i] ≤ 10^9)\) – giá thành và hiệu suất của máy tính thứ \(i\).
Output: LAPTOP.OUT
- Chứa một số nguyên duy nhất là số lượng máy tính đáp ứng yêu cầu của phụ huynh XYZ (theo quan điểm của chuyên gia thứ 3).
Ví dụ:
Input (LAPTOP.INP)
5
3 5
1 2
4 3
6 9
2 1
Output (LAPTOP.OUT)
2
Giải thích ví dụ:
- Máy tính thứ nhất có giá thấp hơn máy tính thứ ba, nhưng hiệu suất lại cao hơn máy tính thứ ba.
- Máy tính thứ hai có giá thấp hơn máy tính thứ năm, nhưng hiệu suất lại cao hơn máy tính thứ năm.
👉 Vậy, hai máy tính mà phụ huynh XYZ có thể lựa chọn là máy tính thứ nhất và thứ hai.
Ràng buộc:
- Subtask 1: 60% test đầu tiên ứng với \(1 \le n\le10^3\).
- Subtask 2: 40% test còn lại không có ràng buộc gì.
Nhận xét