obsidian

POJ 2398 Toy Storage(计算几何)

10
2017/08

# 代码

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f
#define mod 1e9+7
#define clr(a,x) memset(a,x,sizeof(a))
const double eps = 1e-6;
const int N = 50001;
int n,m;
int u[N],l[N];
int ans[N],an[N],bn[N];
int x1,x2,y1,y2;
struct point
{
int x,y;
}a[N];
struct line
{
int u,v;
}b[N];
bool cmp1(point a,point b)
{
return a.x<b.x;
}
bool cmp2(line c,line d)
{
return c.u<d.u;
}
int xmul(int x1,int y1,int x2,int y2)
{
return (x1*y2)-(x2*y1);
}
int main()
{
while(cin>>n,n)
{
cin>>m>>x1>>y1>>x2>>y2;
for(int i=0;i<n;i++)
{
cin>>b[i].u>>b[i].v;
ans[i]=0;
}
ans[n]=0;
sort(b,b+n,cmp2);
for(int i=0;i<m;i++)
{
cin>>a[i].x>>a[i].y;
}
sort(a,a+m,cmp1);
for(int i=0,j;i<m;i++)
{
for(j=0;j<n;j++)
if(xmul(a[i].x-b[j].v,a[i].y-y2,b[j].u-b[j].v,y1-y2)<=0)
break;
++ans[j];
}
for(int i = 1;i <= n;i++)
an[i] = 0;
for(int i = 0;i <= n;i++)
if(ans[i]>0)
an[ans[i]]++;
printf("Box\n");
for(int i = 1;i <= n;i++)
if(an[i]>0)
printf("%d: %d\n",i,an[i]);
}
return 0;
}


Last modification：November 2nd, 2019 at 02:36 pm