POJ2318：TOYS——题解

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

题目大意：给一个大矩形，分成n+1份，求落在每一份的点的数量。

——————————————————

首先叉积可以判断一个点在边界的左边还是右边（不写公式了）

然后边界题中给定按顺序读入，显然是可以二分的，于是二分之。

然后切了。

#include<cstdio>
#include<queue>
#include<cctype>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int K=5005;
typedef double dl;
inline int read(){
    int X=0,w=0;char ch=0;
    while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
    while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
    return w?-X:X;
}
struct point{//既是向量又是点
    int x;
    int y;
}q;
struct line{
    int u;
    int l;
}p[K];
int n,m,x1,y1,x2,y2,ans[K];
inline point getmag(point a,point b){
    point s;
    s.x=b.x-a.x;s.y=b.y-a.y;
    return s;
}
inline int multiX(point a,point b){
    return a.x*b.y-b.x*a.y;
}
int erfen(int l,int r){
    if(l==r)return l-1;
    int mid=(l+r)>>1;
    point a,b;
    a.x=p[mid].u;a.y=y1;
    b.x=p[mid].l;b.y=y2;
    if(multiX(getmag(q,a),getmag(q,b))<0)return erfen(l,mid);
    return erfen(mid+1,r);
}
int main(){
    bool first=0;
    while(scanf("%d",&n)!=EOF&&n){
    if(first)putchar('
');
    first=1;
    memset(ans,0,sizeof(ans));
    int m=read();
    x1=read();y1=read();
    x2=read();y2=read();
    for(int i=1;i<=n;i++){
        p[i].u=read();
        p[i].l=read();
    }
    for(int i=1;i<=m;i++){
        q.x=read();
        q.y=read();
        ans[erfen(1,n+1)]++;
    }
    for(int i=0;i<=n;i++){
        printf("%d: %d
",i,ans[i]);
    }
    }
    return 0;
}