poj2398 Toy Storage
链接
题目大意
这道题的大概意思是先输入6个数字：n,m,x1,y1,x2,y2。n代表卡片的数量，卡片竖直(或倾斜）放置在盒内，可把盒子分为n+1块区域，然后分别用0到n表示，m代表玩具的个数，（x1,y1）代表盒子的左上顶点坐标，(x2,y2)代表盒子的右下顶点坐标，接下来的n行，每行都有两个数a，b，(a,y1)，(b,y2)分别代表卡片的两个顶点位置，接下来的m行每行两个数从c,d，(c,d),代表玩具放置的坐标，最后让你输出当区域内玩具的个数（递增，0除外），以及有几个同样数目玩具的区域，当输入第一个数为0时结束。
思路
先把隔板排序。
然后每个玩具二分位置。用叉积判断。
代码
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
const int N=1005;
const double eps=1e-10;
struct point {
double x,y;
}a[N],b[N];
point operator - (point a,point b) {
return (point){a.x-b.x,a.y-b.y};
}
double operator * (point a,point b) {
return a.x*b.y-b.x*a.y;
}
struct line {
double u,l;
}l[N];
int n,m;
bool cmp(line a,line b) {
return a.u<b.u;
}
int cnt[N],ans[N];
int main() {
while(scanf("%d",&n)!=EOF&&n) {
scanf("%d",&m);
scanf("%lf%lf%lf%lf",&b[0].x,&b[0].y,&a[n+1].x,&a[n+1].y);
a[0].x=b[0].x,a[0].y=b[n+1].y;
b[n+1].x=a[n+1].x,b[n+1].y=b[0].y;
for(int i=1;i<=n;++i)
scanf("%lf%lf",&l[i].u,&l[i].l);
sort(l+1,l+1+n,cmp);
for(int i=1;i<=n;++i) {
a[i].x=l[i].l,a[i].y=a[n+1].y;
b[i].x=l[i].u,b[i].y=b[0].y;
}
memset(cnt,0,sizeof(cnt));
memset(ans,0,sizeof(ans));
for(int i=1;i<=m;++i) {
point c;
scanf("%lf%lf",&c.x,&c.y);
if(!(a[n+1].y<=c.y&&c.y<=b[0].y&&b[0].x<=c.x&&c.x<=a[n+1].x)) continue;
int l=0,r=n+1;
while(l+1!=r) {
int mid=(l+r)>>1;
if((b[mid]-a[mid])*(c-a[mid])>0) r=mid;
else l=mid;
}
cnt[l+1]++;
}
puts("Box");
for(int i=1;i<=n+1;++i)
if(cnt[i]) ans[cnt[i]]++;
for(int i=1;i<=m;++i)
if(ans[i]) printf("%d: %d
",i,ans[i]);
}
return 0;
}