Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
MRECT1 - Point on the side of the rectangle |
English | Vietnamese |
Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/mrect1
The government is planing to build a walkway for tourists in the middle of an oak forest. The forest
can be represented as plane with N special lattice points representing oaks.
rectangle intersect any oak lattice points, such oaks need to be axed down. Oaks inside the rectangle
not represent problems and need not be cut do
Ljubo is the state secretary of Forestry and an passionate nature lover, so he ordered the secretary of
Tourism to provide him with a list of P possible rectangle walkways that are attractive enough to draw
Cho N điểm và P hình chữ nhật trên mặt phẳng tọa độ. Tính xem với mỗi hình chữ nhật có bao nhiêu
điểm nằm ở trên cạnh của nó trong P điểm đã cho.
Input
Dòng đầu ghi số điểm N (1 ≤ N ≤ 300 000), N dòng tiếp theo mỗi dòng ghi 2 số X, Y (1 ≤ X, Y ≤ 10^9) . Không có hai điểm nào trùng nhau.
Dòng tiếp theo ghi số P, (1 ≤ P ≤ 100 000), số hình chữ nhật.
P dòng tiếp theo, mỗi dòng ghi 4 số X1, Y1, X2 , Y2 (1 ≤ X1 < X2 ≤ 10^9, 1 ≤ Y1 < Y2 ≤ 10^9)
là tọa độ góc trái dưới (X1, Y1) và góc phải trên (X2, Y2) của từng hình chữ nhật.
Output
Ghi ra P số nguyên, mỗi số trên 1 dòng, là số điểm nằm trên cạnh của từng hình chữ nhật.
Sample
input
6
1 2
3 2
2 3
2 5
4 4
6 3
4
2 2 4 4
2 2 6 5
3 3 5 6
5 1 6 6
output
3
4
0
1
in tourists.
Ljubo plans to select the walkway that needs the smallest amount of oak trees to be cut down. Since we
also like trees, would you be so kind and write a program that will determine the number of oaks that
will be cut down for each walkway. Remember only the oaks intersecting the sides of the rectangle
need to be cut.
Được gửi lên bởi: | psetter |
Ngày: | 2010-05-24 |
Thời gian chạy: | 1s |
Giới hạn mã nguồn: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Ngôn ngữ cho phép: | Tất cả ngoại trừ: GOSU NODEJS OBJC PERL6 PYPY RUST SED SQLITE VB.NET |
Nguồn bài: | COI 2010 |
hide comments
2018-07-12 17:05:16
1 đấm ac |
|
2017-06-21 22:23:23
n.log(n) TLE -_- |
|
2014-06-11 12:25:07 Chuyên Nhật CNN
9 cái tìm kiếm nhị phân trong 1 bài ;-; feeling so noob |
|
2010-06-14 13:23:14 Hy Trường Sơn
@~!(*(@*!@^&: Em cam on anh ^^ |
|
2010-05-29 17:09:44 ~!(*(@*!@^&
@Son: Dung scanf, ko cin. |