首页 > 代码库 > poj2318 TOYS 【计算几何】【点和线的关系】

poj2318 TOYS 【计算几何】【点和线的关系】

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

题目大意:给你n,m,x1,y1,x2,y2表示的分别是n个线,m个点,(x1,y1)表示的是矩形左上角那个点,(x2,y2)表示的是矩形右下角那个点。

然后给出n个线(L)的x坐标L.s.x,L.e.x,就相当于是给出了线的位置,下面给出m个点的坐标。

最后问n条线分成的n+1个区域内各有多少个点。

题目不是很难,不过与二分结合起来还是有点意思的。

注意叉乘的性质,在什么时候叉乘的结果会是小于0什么时候会是大于0。

如果是顺时针的话叉乘的结果就是大于0,如果是逆时针的话叉乘结果小于0。

#include<iostream>
#include<stdio.h>
#include<cstring>
using namespace std;
struct point {
    double x;double y;
    point(const double &x = 0, const double &y = 0):x(x), y(y){} //注意最后两个字母别打错了
    void in(){scanf("%lf%lf",&x,&y);}
    void out()const{ printf("%.2lf %.2lf\n",x,y);}
}s,e;

struct line{
    point s;
    point e;
};

int n,m; //n条线(分成n+1个区域) m个玩具 最后输出每个区域内的玩具个数
line L[5005];
point P;
int cnt[5005];

//计算叉乘(P1-P0)X(P2-P0)
double xmult(point p1,point p2,point p0){
    return (p1.x-p0.x)*(p2.y-p0.y) - (p1.y-p0.y)*(p2.x-p0.x);
}

void B_search(point P){
    int l=0,r=n-1,mid;
    while(l<r){
        mid = (l+r)/2;
        if(xmult(P,L[mid].s,L[mid].e) > 0) l = mid + 1;
        else r = mid;
}
    if(xmult(P,L[l].s,L[l].e)<0) cnt[l]++;
    else cnt[l+1]++;
}

int main ()
{
    while(~scanf("%d",&n)){
        memset(cnt,0,sizeof(cnt));
        if(n==0) break;
        scanf("%d %lf %lf %lf %lf",&m,&s.x,&s.y,&e.x,&e.y);
        for(int i=0;i<n;i++){
            double t1,t2;
            scanf("%lf %lf",&t1,&t2);
            L[i].s.x=t1;
            L[i].s.y=s.y;
            L[i].e.x=t2;
            L[i].e.y=e.y;
        }
        for(int i=0;i<m;i++){
            scanf("%lf %lf",&P.x,&P.y);
            B_search(P);
        }
        for(int i=0;i<=n;i++) cout<<i<<": "<<cnt[i]<<endl;
        cout<<endl;
    }
}




poj2318 TOYS 【计算几何】【点和线的关系】