蛋疼無聊來發(fā)個(gè)水題
題意：給定N個(gè)點(diǎn)，M個(gè)詢問，每次詢問(x1,y1)與(x2,y2)為對(duì)點(diǎn)構(gòu)成的正方形嚴(yán)格邊緣上有多少個(gè)點(diǎn)。
做法：
把問題轉(zhuǎn)化成求一條線段上的點(diǎn)個(gè)數(shù) 對(duì)于每個(gè)詢問只要查找四條直線上有多少點(diǎn)即可。
這個(gè)很簡(jiǎn)單，排序+二分即可。（注意處理細(xì)節(jié)，最好想好區(qū)間的開閉再寫）
我偷懶用了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