蛋疼无聊来发个水题
题意：给定N个点，M个询问，每次询问(x1,y1)与(x2,y2)为对点构成的正方形严格边缘上有多少个点。
做法：
把问题转化成求一条线段上的点个数 对于每个询问只要查找四条直线上有多少点即可。
这个很简单，排序+二分即可。（注意处理细节，最好想好区间的开闭再写）
我偷懒用了lower_bound和upper_bound..
1 #include <cstdio>
2 #include <vector>
3 #include <cstdlib>
4 #include <algorithm>
5 using namespace std;
6 vector<pair<int,int> > X,Y;
7 int N,Que,x,y,x1,y1,x2,y2;
8 inline int Q_fow(vector<pair<int,int> > &P,int x,int y1,int y2)
9 {
10 return upper_bound(P.begin(),P.end(),make_pair(x,y2))-upper_bound(P.begin(),P.end(),make_pair(x,y1));
11 }
12 inline int Q_rev(vector<pair<int,int> > &P,int x,int y1,int y2)
13 {
14 return lower_bound(P.begin(),P.end(),make_pair(x,y2))-lower_bound(P.begin(),P.end(),make_pair(x,y1));
15 }
16 int main()
17 {
18 scanf("%d",&N);
19 for (int i=0;i<N;++i)
20 {
21 scanf("%d%d",&x,&y);
22 X.push_back(make_pair(x,y));
23 Y.push_back(make_pair(y,x));
24 }
25 sort(X.begin(),X.end());
26 sort(Y.begin(),Y.end());
27 scanf("%d",&Que);
28 for (;Que--;)
29 {
30 scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
31 printf("%d\n",Q_fow(X,x1,y1,y2)+Q_fow(Y,y2,x1,x2)+Q_rev(X,x2,y1,y2)+Q_rev(Y,y1,x1,x2));
32 }
33 return 0;
34 }
35