MRECT1 - Point on the side of the rectangle

 

 

English Vietnamese

 




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.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.