poj2318（叉积判断点在直线左右+二分）

题目链接：https://vjudge.net/problem/POJ-2318

题意：有n条线将矩形分成n+1块，m个点落在矩形内，求每一块点的个数。

思路：

　　最近开始肝计算几何，之前的几何题基本处于挂机状态，但听别人说几何题不会太难，所以打算把几何给过了。

　　先引入叉积的一个重要性质，O为原点：

　　　　OP^OQ>0 : P在Q的顺时针方向。

　　　　OP^OQ<0 : P在Q的逆时针方向。

　　　　OP^OQ=0 : O,P,Q共线。

　　那么我们就可以利用该性质判断一个点P在直线AB的左侧当且仅当：PA^PB<0。

　　再发现可以用二分查找第一条满足点在直线左侧的直线即可，其单调性显然可知。

AC code：

#include<cstdio>

#include<algorithm>

using namespace std;

const int maxn=;

int n,m,x1,y1,x2,y2,ans[maxn],flag=;

struct Point{

    int x,y;

    Point(){}

    Point(int xx,int yy):x(xx),y(yy){}

    Point operator + (const Point& b)const{

        return Point(x+b.x,y+b.y);

    }

    Point operator - (const Point& b)const{

        return Point(x-b.x,y-b.y);

    }

    int operator * (const Point& b)const{

        return x*b.x+y*b.y;

    }

    int operator ^ (const Point& b)const{

        return x*b.y-b.x*y;

    }

};

struct Line{

    Point s,e;

    Line(){};

    Line(Point ss,Point ee){

        s=ss,e=ee;

    }

}line[maxn];

int check(int x,int y,int m){

    Point pt=Point(x,y);

    return (line[m].s-pt)^(line[m].e-pt);

}

int main(){

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

        if(flag) flag=;

        else printf("\n");

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

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

            ans[i]=;

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

            int u,l;

            scanf("%d%d",&u,&l);

            line[i]=Line(Point(u,y1),Point(l,y2));

        }

        line[n]=Line(Point(x2,y1),Point(x2,y2));

        while(m--){

            int x,y;

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

            Point pt=Point(x,y);

            int l=,r=n,mid;

            while(l<=r){

                mid=(l+r)>>;

                if(check(x,y,mid)<=) r=mid-;

                else l=mid+;

            }

            ++ans[l];

        }

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

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

    }

}

巴特西

poj2318（叉积判断点在直线左右+二分）

最新文章

热门文章