题目:题目链接
题目的意思就是说给你一个方格子,里面用n条线隔开了。现在给你n个玩具的坐标,这些玩具肯定在方格里面,让你求每一个方格里面有多少个玩具。
叉积+二分搜索。由于点必定在格子中,因此,用目标点和格子边上的四个点进行叉积运算,点在格子的“左边”的右边且在格子的“右边”的左边时,即在该格子中,否则,根据叉积结果二分搜索。
代码:
#include <iostream> #include <cstdio> #include <string> #include <string.h> #include <map> #include <vector> #include <cstdlib> #include <cmath> #include <algorithm> #include <queue> #include <set> #include <stack> using namespace std; const int M=50200; const double eps=1e-6; struct point { int x,y; } p; struct rec { point p[4]; } r[M]; int cnt[M]; int n,m; void init() { for(int i=0; i<=n+1; i++) cnt[i] = 0; } double cross(double x1,double y1,double x2,double y2) { return x1*y2-x2*y1; } void search() { int low=0,high=n; bool flag=false; while(low<=high) { int mid=(low+high)>>1; double temp1=cross(r[mid].p[0].x-p.x,r[mid].p[0].y-p.y,r[mid].p[1].x-p.x,r[mid].p[1].y-p.y); double temp2=cross(r[mid].p[3].x-p.x,r[mid].p[3].y-p.y,r[mid].p[2].x-p.x,r[mid].p[2].y-p.y); if(temp1>=eps && temp2<=-eps) { cnt[mid]++; return ; } if(temp2 > eps) low=mid+1; else high=mid-1; } } int main() { while(scanf("%d",&n)==1) { if(!n) break; init(); scanf("%d",&m); scanf("%d%d%d%d",&r[0].p[0].x,&r[0].p[0].y,&r[n].p[2].x,&r[n].p[2].y); r[0].p[1].x=r[0].p[0].x; r[0].p[1].y=r[n].p[2].y; r[n].p[3].x=r[n].p[2].x; r[n].p[3].y=r[0].p[0].y; for(int i=1; i<=n; i++) { scanf("%d%d",&r[i].p[0].x,&r[i].p[1].x); r[i].p[0].y =r[i-1].p[0].y; r[i].p[1].y =r[i-1].p[1].y; r[i-1].p[3].x =r[i].p[0].x; r[i-1].p[3].y =r[i].p[0].y; r[i-1].p[2].x =r[i].p[1].x; r[i-1].p[2].y =r[i].p[1].y; } for(int i=0; i<m; i++) { scanf("%d%d",&p.x,&p.y); search(); } for(int i=0; i<=n; i++) { printf("%d: %d\n",i,cnt[i]); } printf("\n"); } return 0; }
努力努力...