題目意思很簡單，把一個盒子分成很多部分，往盒子里扔小球，小球的落點當然要告訴你拉，讓你統計每個盒子里最后擁有的小球數。
我的做法是叉積+二分。
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
struct Point
{ // 二維點或矢量
double x, y;
Point() {}
Point(double x0, double y0): x(x0), y(y0) {}
};
struct Line
{ // 二維的直線或線段
Point p1, p2;
Line() {}
Line(Point p10, Point p20): p1(p10), p2(p20) {}
};
double multiply(Point sp,Point ep,Point op)
{
return((sp.x-op.x)*(ep.y-op.y) - (ep.x-op.x)*(sp.y-op.y));
}
Line myline[5100];
int record[5100];
int main()
{
int n,m,i;
Point left;
Point right;
while(scanf("%d",&n))
{
if(n==0)
break;
memset(record,0,sizeof(record));
scanf("%d%lf%lf%lf%lf",&m,&left.x,&left.y,&right.x,&right.y);
myline[0].p1.x=left.x;
myline[0].p1.y=right.y;
myline[0].p2.x=left.x;
myline[0].p2.y=left.y;
for(i=1;i<=n;i++)
{
scanf("%lf%lf",&myline[i].p2.x,&myline[i].p1.x);
myline[i].p1.y=right.y;
myline[i].p2.y=left.y;
}
myline[n+1].p1.x=right.x;
myline[n+1].p1.y=right.y;
myline[n+1].p2.x=right.x;
myline[n+1].p2.y=left.y;
Point toy;
for(i=1;i<=m;i++)
{
scanf("%lf%lf",&toy.x,&toy.y);
int front=0;
int rear=n+1;
while(front<=rear)
{
int mid=(front+rear)>>1;
if(multiply(toy,myline[front].p2,myline[front].p1)>0&&multiply(toy,myline[mid].p2,myline[mid].p1)<0)
{
if(mid==front+1)
{
record[front]++;
break;
}
rear=mid;
continue;
}
else
{
if(mid+1==rear)
{
record[mid]++;
break;
}
front=mid;
continue;
}
}
}
for(i=0;i<=n;i++)
{
printf("%d: %d\n",i,record[i]);
}
printf("\n");
}
return 0;
}
恭喜此題成為我收集計算幾何模板的第一題 呵呵~