首页 > 代码库 > POJ 1066 Treasure Hunt 线段相交判断

POJ 1066 Treasure Hunt 线段相交判断

判断以宝藏的坐标和中点的坐标为线段的点是否与墙相交,求最少相交的墙的数量

中点算出来,枚举中点和墙

#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>#define eps 1e-8#define INF 1e9using namespace std;const int maxn=100;typedef struct Point{    double x,y;    Point() {};    Point(double xx,double yy)    {        x=xx;        y=yy;    }} Vector;struct Line{    Point p,q;    Line() {};    Line(Point pp,Point qq)    {        p=pp;        q=qq;    }};int sgn(double x){    if(fabs(x)<eps) return 0;    return x<0? -1:1;}double crs_prdct(Vector a,Vector b){    return a.x*b.y-b.x*a.y;}double dot_prdct(Vector a,Vector b){    return a.x*a.y+b.x*b.y;}Point mid_point(Point a,Point b){    return Point((a.x+b.x)/2,(a.y+b.y)/2);}Vector operator - (Point a,Point b){    return Vector(a.x-b.x,a.y-b.y);}bool operator == (Point a,Point b){    return a.x==b.x && a.y==b.y;}bool inter(Line l1,Line l2){    return        max(l1.p.x,l1.q.x) >= min(l2.p.x,l2.q.x) &&        max(l2.p.x,l2.q.x) >= min(l1.p.x,l1.q.x) &&        max(l1.p.y,l1.q.y) >= min(l2.p.y,l2.q.y) &&        max(l2.p.y,l2.q.y) >= min(l1.p.y,l1.q.y) &&        sgn(crs_prdct(l2.p-l1.p,l1.q-l1.p))*sgn(crs_prdct(l2.q-l1.p,l1.q-l1.p))<=0 &&        sgn(crs_prdct(l1.p-l2.p,l2.q-l1.p))*sgn(crs_prdct(l1.q-l2.p,l2.q-l2.p))<=0;}bool cmp(Point a,Point b){    if(a.x==b.x) return a.y<b.y;    return a.x<b.x;}Line line[maxn];Point mid[4*maxn];Point a[4][maxn];int main(){//    freopen("in.txt","r",stdin);    int n;    while(scanf("%d",&n)!=EOF)    {        double x1,y1,x2,y2;        for(int i=0;i<n;i++)        {            scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);            line[i]=Line(Point(x1,y1),Point(x2,y2));        }        Point p;        scanf("%lf%lf",&p.x,&p.y);        a[0][0]=Point(0,0);        a[1][0]=Point(0,0);        a[2][0]=Point(0,100);        a[3][0]=Point(100,0);        int cnt[4]={1,1,1,1};        for(int i=0;i<n;i++)        {            if(line[i].p.y==0) a[0][cnt[0]++]=Point(line[i].p.x,0);            if(line[i].q.y==0) a[0][cnt[0]++]=Point(line[i].q.x,0);            if(line[i].p.x==0) a[1][cnt[1]++]=Point(0,line[i].p.y);            if(line[i].q.x==0) a[1][cnt[1]++]=Point(0,line[i].q.y);            if(line[i].p.y==100) a[2][cnt[2]++]=Point(line[i].p.x,100);            if(line[i].q.y==100) a[2][cnt[2]++]=Point(line[i].q.x,100);            if(line[i].p.x==100) a[3][cnt[3]++]=Point(100,line[i].p.y);            if(line[i].q.x==100) a[3][cnt[3]++]=Point(100,line[i].q.y);        }        a[0][cnt[0]++]=Point(100,0);        a[1][cnt[1]++]=Point(0,100);        a[2][cnt[2]++]=Point(100,100);        a[3][cnt[3]++]=Point(100,100);        for(int i=0;i<4;i++)            sort(a[i],a[i]+cnt[i],cmp);        int cnt2=0;        for(int i=0;i<4;i++)            for(int j=0;j<cnt[i]-1;j++)                if(!(a[i][j]==a[i][j+1]))                    mid[cnt2++]=mid_point(a[i][j],a[i][j+1]);        int ans=INF;        for(int i=0;i<cnt2;i++)        {            int tmp=0;            for(int j=0;j<n;j++)                if(inter(Line(p,mid[i]),line[j])) tmp++;            ans=min(ans,tmp);        }        printf("Number of doors = %d \n",ans+1);    }    return 0;}

 

POJ 1066 Treasure Hunt 线段相交判断