首页 > 代码库 > poj 2398 Toy Storage

poj 2398 Toy Storage

2024-08-04 04:20:37   221人阅读

http://poj.org/problem?id=2398

题意：一个矩形盒子，在里面用多个板子把这个矩形盒子分成多部分，然后给你多个点，判断这些点在每个盒子有多少个点。

思路：根据给出板子的坐标，对这些板子的坐标排序，然后记录每一个被分出的小矩形的四个点，输入每一个点的时候判断在哪一个小矩形里面，用二分快速找到，在哪一个矩形里面的条件是在小矩形的左的边的右边，右的边的左边。

 1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 const double eps=1e-8; 6  7 int n,m; 8 double x1,y1,x2,y2; 9 int num[20000];10 int ans[200000];11 struct point12 {13     double x,y;14 };15 16 struct node17 {18     point s,t;19     bool operator <(const node &a)const20     {21         return s.x<a.s.x;22     }23 }l[20000];24 25 double cross(double x1,double y1,double x2,double y2)26 {27     return x1*y2-y1*x2;28 }29 struct node130 {31     point p[4];32 }c[2000];33 34 int main()35 {36     while(scanf("%d",&n)!=EOF)37     {38         if(n==0) break;39         memset(num,0,sizeof(num));40         memset(ans,0,sizeof(ans));41         scanf("%d%lf%lf%lf%lf",&m,&x1,&y1,&x2,&y2);42         c[0].p[0].x=x1;c[0].p[0].y=y1;43         c[0].p[1].x=x1; c[0].p[1].y=y2;44         c[n].p[3].x=x2; c[n].p[3].y=y1;45         c[n].p[2].x=x2; c[n].p[2].y=y2;46         for(int i=0; i<n; i++)47         {48             double ui,li;49             scanf("%lf%lf",&ui,&li);50             l[i].s.x=ui; l[i].s.y=y1;51             l[i].t.x=li; l[i].t.y=y2;52         }53         sort(l,l+n);54         for(int i=0; i<n; i++)55         {56             c[i].p[2]=l[i].t;57             c[i].p[3]=l[i].s;58             c[i+1].p[0]=l[i].s;59             c[i+1].p[1]=l[i].t;60         }61         for(int i=1; i<=m; i++)62         {63             double x,y;64             scanf("%lf%lf",&x,&y);65             int l=0,r=n;66             while(l<=r)67             {68                 int mid=(l+r)>>1;69                 double t1=cross(c[mid].p[0].x-x,c[mid].p[0].y-y,c[mid].p[1].x-x,c[mid].p[1].y-y);70                 double t2=cross(c[mid].p[3].x-x,c[mid].p[3].y-y,c[mid].p[2].x-x,c[mid].p[2].y-y);71                 if(t1>=eps&&t2<=-eps)72                 {73                     num[mid]++;74                     break;75                 }76                 else if(t2>=eps)77                 {78                     l=mid+1;79                 }80                 else81                     r=mid-1;82             }83         }84         for(int i=0; i<=n; i++)85         {86            if(num[i]>0)87            ans[num[i]]++;88         }89         printf("Box\n");90         for(int i=1; i<=n; i++)91         {92             if(ans[i]>0)93             {94                 printf("%d: %d\n",i,ans[i]);95             }96         }97     }98     return 0;99 }
View Code

 

poj 2398 Toy Storage


联系
我们