题目链接:点击打开链接
题目分析：poj 2398和poj 2318一致
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
struct point
{
int x,y;
point(int a=0,int b=0)
{
x=a;
y=b;
}
} part[2220],u_left,l_right,node[1010];
struct info
{
int x1,x2;
}data[1010];
int ans[1010];
int cmp(point a,point b)
{
return a.x<b.x;
}
int cmp2(info a,info b)
{
return min(a.x1,a.x2)<min(b.x1,b.x2);
}
int cross(point p0,point p1,point p2)
{
return ((p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y));
}
int n,m;
void solve()
{
int j=0;
for(int i=0; i<m; i++)
{
for(j=0; j<=2*n;)
{
if(cross(part[j+1],node[i],part[j])>0&&cross(part[j+3],part[j+2],node[i])>0)
{
ans[j/2]++;
break;
}
else j+=2;
}
}
}
int xmp(int x,int y)
{
return x<y;
}
int main()
{
while(~scanf("%d%d%d%d%d%d",&n,&m,&u_left.x,&u_left.y,&(l_right.x),&(l_right.y))&&n)
{
int u,l;
part[0].x=u_left.x, part[0].y=u_left.y;
part[1].x=u_left.x, part[1].y=l_right.y;
for(int j=0;j<n;j++)
{
scanf("%d %d",&data[j].x1,&data[j].x2);
}
sort(data,data+n,cmp2);
for(int i=2; i<=2*n; i+=2)
{
part[i].x=data[i/2-1].x1 , part[i].y=u_left.y;
part[i+1].x=data[i/2-1].x2 , part[i+1].y=l_right.y;
}
part[2*n+2].x=l_right.x , part[2*n+2].y=u_left.y;
part[2*n+3].x=l_right.x , part[2*n+3].x=l_right.x;
for(int j=0; j<m; j++)
{
scanf("%d %d",&node[j].x,&node[j].y);
}
sort(node,node+m,cmp);
memset(ans,0,sizeof(ans));
solve();
sort(ans,ans+n+1,xmp);
int t=ans[0],count=0;
printf("Box\n");
for(int i=0;i<=n;i++)
{
if(ans[i]==0)
{t=ans[i+1];continue;}
else if(ans[i]==t) {t=ans[i+1];count++;}
if(ans[i]!=t||i==n)
{
printf("%d: %d\n",ans[i],count);
count=0;
}
}
}
return 0;
}