Omni Inspirations

problems & programs ~

统计

留言簿

Friends

阅读排行榜

评论排行榜

COI 2010 hrastovi

蛋疼无聊来发个水题

题意:给定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 

posted on 2010-06-20 14:07 jsn1993 阅读(269) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理