2318 - TOYS

ForTest

題目：http://poj.org/problem?id=2318
AC Code：http://ideone.com/gvN0dV

寒訓計算幾何題(說明待補)

Submission id:12499327 Status:AC
http://poj.org/status?result=0&user_id=Lucifer1998

#include <cstdio>

#include <cstring>

using namespace std;

struct data{

        double x,y;

        data(){}

        data(int _x,int _y): x(_x),y(_y){}

        data operator-(data a)const{return data(x - a.x , y - a.y);}

        data operator+(data a)const{return data(x + a.x , y + a.y);}

        bool operator^(data a)const{return x * a.y - y * a.x > 0;}

};

int n,m,lx,ly,rx,ry;

data d[7000];

int a[7000],b[7000],ans[7000];

int lower(data ask){

        int l = 0,r = n+1,mid;

        while(r - l >1){

                mid  = (l+r)/2;

                if(d[mid] ^ data(ask.x - b[mid], ask.y - ry))r = mid;

                else l = mid;

        }

        return r;

}

int main(){

        while(~scanf("%d",&n),n){

                scanf("%d%d%d%d%d",&m,&lx,&ly,&rx,&ry);

                for(int i= 1;i<=n;++i){

                        scanf("%d%d",&a[i],&b[i]);

                        d[i] = data(a[i] - b[i] , ly - ry);

                }

                a[0] = b[0] = lx;

                d[0] = data(0,ly-ry);

                a[n+1] = b[n+1] = rx;

                d[n+1] = data (0,ly - ry);

                memset(ans,0,sizeof ans);

                for(int i=0;i<m;++i){

                        int x,y;

                        scanf("%d%d",&x,&y);

                        ans[lower(data(x,y))]++;

                }

                for(int i=1;i<=n+1;++i){

                        printf("%d: %d\n",i-1,ans[i]);

                }

                puts("");

        }

}