poj2318 水题（二分+叉积）

题目链接：http://poj.org/problem?id=2318

#include<cstdio>

#include<cstring>

#include<cmath>

#include<iostream>

#include<algorithm>

#include<queue>

using namespace std;

const int maxn = ;

const int maxe = ;

const int INF = 0x3f3f3f;

const double eps = 1e-;

const double PI = acos(-1.0);

struct Point{

    double x,y;

    Point(double x=, double y=) : x(x),y(y){ }    //构造函数

};

typedef Point Vector;

Vector operator + (Vector A , Vector B){return Vector(A.x+B.x,A.y+B.y);}

Vector operator - (Vector A , Vector B){return Vector(A.x-B.x,A.y-B.y);}

Vector operator * (Vector A , double p){return Vector(A.x*p,A.y*p);}

Vector operator / (Vector A , double p){return Vector(A.x/p,A.y/p);}

bool operator < (const Point& a,const Point& b){

    return a.x < b.x ||( a.x == b.x && a.y < b.y);

}

int dcmp(double x){

    if(fabs(x) < eps) return ;

    else              return x <  ? - : ;

}

bool operator == (const Point& a, const Point& b){

    return dcmp(a.x - b.x) ==  && dcmp(a.y - b.y) == ;

}

double Dot(Vector A, Vector B){ return A.x*B.x + A.y*B.y; }

double Cross(Vector A, Vector B)  { return A.x*B.y - A.y * B.x; }

double Length(Vector A)    { return sqrt(Dot(A,A)); }

/******************************分割线*******************************/

Point P[maxn][];

int N,M;

int main()

{

   //freopen("E:\\acm\\input.txt","r",stdin);

   while(scanf("%d",&N)== && N){

        scanf("%d",&M);

        double x1,y1,x2,y2;

        scanf("%lf %lf %lf %lf",&x1,&y1,&x2,&y2);

        P[][] = Point(x1,y2);   P[][] = Point(x1,y1);

        P[N+][] = Point(x2,y2); P[N+][] = Point(x2,y1);

        for(int i=;i<=N;i++){

            double Ui,Li;

            scanf("%lf %lf",&Ui,&Li);

            P[i][] = Point(Li,y2);  P[i][] = Point(Ui,y1);

        }

        int num[maxn];

        memset(num,,sizeof(num));

        for(int i=;i<=M;i++){

            Point A;

            scanf("%lf %lf",&A.x,&A.y);

            int L=, R=N+;

            while(L < R-){

                int mid = L + (R-L)/;

                if(dcmp(Cross(P[mid][]-P[mid][],A-P[mid][])) > )  R = mid;

                else                                                  L = mid;

            }

            num[L]++;

        }

        for(int i=;i<=N;i++){

            printf("%d: %d\n",i,num[i]);

        }

        printf("\n");

   }

}