首页 > 代码库 > poj2318TOYS

poj2318TOYS

2024-07-05 17:36:55   224人阅读

题意：一个矩形被相对位置严格递增的线段分成n+1块，（线段中不会有相交的），给m个点，判断他们属于哪个区域。点不会在中间的分界线上，但可能在矩形的边线上。

解题思路：首先是，如何判断一个点在线段的哪侧，这个可以用叉积来做。如果PP1*PP2<0那么P在P1P2的右侧。其实PP1*PP2<0判断的是PP1和PP2的位置关系，表示从PP1转向PP2为逆时针（转角小于180度）。

      第二就是判断一个点在哪个区域里，由于点和线段只有两种位置关系，所以判断点在那个区域，可以转化成判断点和线段的位置关系。由于线段位置严格单调递增，我们可以采用二分的方法来判断点在哪个线段的左侧！（就是找到两个相邻的线段，该点和两线段一个叉积大于0，一个小于0）。当然对于最前面和最后面也要特殊考虑，可以在前后各加一个线段。

  1 //Accepted    348 KB    141 ms    
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cmath>
  5 const int MAXN = 5005;
  6 struct node
  7 {
  8     double x,y;
  9     node()
 10     {
 11 
 12     }
 13     node(double x,double y):x(x),y(y)
 14     {
 15 
 16     }
 17     struct node operator-(struct node t)
 18     {
 19         return node(x-t.x,y-t.y);
 20     }
 21     struct node operator+(struct node t)
 22     {
 23         return node(x+t.x,y+t.y);
 24     }
 25     double operator*(struct node t)
 26     {
 27         return (x*t.y-y*t.x);
 28     }
 29 };
 30 struct line
 31 {
 32     node p1,p2;
 33 };
 34 line L[MAXN];
 35 node query_node;
 36 node ul,lr;
 37 int num[MAXN];
 38 int n,m;
 39 void read()
 40 {
 41     scanf("%d",&m);
 42     scanf("%lf%lf%lf%lf",&ul.x,&ul.y,&lr.x,&lr.y);
 43     L[0].p1.x=ul.x-1;
 44     L[0].p1.y=ul.y;
 45     L[0].p2.x=ul.x-1;
 46     L[0].p2.y=lr.y;
 47     for (int i=1;i<=n;i++)
 48     {
 49         scanf("%lf%lf",&L[i].p1.x,&L[i].p2.x);
 50         L[i].p1.y=ul.y;
 51         L[i].p2.y=lr.y;
 52     }
 53     L[n+1].p1.x=lr.x+1;
 54     L[n+1].p1.y=ul.y;
 55     L[n+1].p2.x=lr.x+1;
 56     L[n+1].p2.y=lr.y;
 57 }
 58 double judge(node p,line pL)
 59 {
 60     return (pL.p1-p)*(pL.p2-p);
 61 }
 62 int binary_search()
 63 {
 64     int l=0,r=n+1;
 65     int mid;
 66     while (l<r)
 67     {
 68         mid=(l+r+1)/2;
 69         if (judge(query_node,L[mid])<1e-9)
 70         {
 71             r=mid-1;
 72         }
 73         else
 74         {
 75             l=mid;
 76         }
 77     }
 78     return l;
 79 }
 80 void slove()
 81 {
 82     read();
 83     memset(num,0,sizeof(num));
 84     for (int i=0;i<m;i++)
 85     {
 86         scanf("%lf%lf",&query_node.x,&query_node.y);
 87         int ans=binary_search();
 88         //printf("ans=%d\n",ans);
 89         num[ans]++;
 90     }
 91     for (int i=0;i<=n;i++)
 92     {
 93         printf("%d: %d\n",i,num[i]);
 94     }
 95 }
 96 int main()
 97 {
 98     int flag=1;
 99     while (scanf("%d",&n),n)
100     {
101         if (flag!=1) printf("\n");
102         flag=0;
103         slove();
104     }
105     return 0;
106 }
View Code

 


联系
我们