poj2318 TOYS

题目描述：

vjudge

POJ

题解：

计算几何，叉积判断方向。

然后整体二分即可。

#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 5050;
const double eps = 1e-8;
struct Point
{
    double x,y;
    Point(){}
    Point(double x,double y):x(x),y(y){}
    Point operator - (const Point&a)const{return Point(x-a.x,y-a.y);}
    double operator ^ (const Point&a)const{return x*a.y-y*a.x;}
};
typedef Point Vector;
struct Line
{
    Point p;
    Vector v;
    Line(){}
    Line(Point p,Vector v):p(p),v(v){}
};
Line s[N];
int n,m;
double x_1,y_1,x_2,y_2;
int dcmp(double x)
{
    if(fabs(x)<=eps)return 0;
    return x>0?1:-1;
}
bool Onleft(Line l,Point p)
{
    return dcmp(l.v^(p-l.p))>0;
}
void dv(int l,int r,vector<Point>&ve)
{
    if(l==r)
    {
        printf("%d: %d
",l,ve.size());
        return ;
    }
    int mid = ((l+r)>>1)+1;
    vector<Point>vl,vr;
    for(int i=0,lim=(int)ve.size();i<lim;i++)
        if(Onleft(s[mid],ve[i]))vl.push_back(ve[i]);
        else vr.push_back(ve[i]);
    dv(l,mid-1,vl);
    dv(mid,r,vr);
}
int main()
{
    while(scanf("%d%d%lf%lf%lf%lf",&n,&m,&x_1,&y_1,&x_2,&y_2)==6)
    {
        double x,y;
        for(int i=1;i<=n;i++)
        {
            scanf("%lf%lf",&x,&y);
            s[i] = Line(Point(y,y_2),Point(x,y_1)-Point(y,y_2));
        }
        vector<Point>v0;
        for(int i=1;i<=m;i++)
        {
            scanf("%lf%lf",&x,&y);
            v0.push_back(Point(x,y));
        }
        dv(0,n,v0);
        puts("");
    }
    return 0;
}