首页 > 代码库 > POJ 3304

POJ 3304

2024-07-13 20:04:03   221人阅读

题目可以转化成是否存在这样的一条直线，穿过所有的线段。这是很容易就能想到的。

然后，假如只有一个端点重合，那么我们可以知道，必定会有属于两条线段的某两个端点连出的直线可以穿过所有线段。这是枚举的思想。

那么，我们该怎么判定直线与线段有交点呢？不妨通过跨立的定义来做，这是经人点醒了才想到的。

在求线段是否有交点的时候用到过跨立，但我认为，跨立的定义应该是延长的线后是否存在交点（当前包括开始就存在交点的。）

假设枚举两点得到的线段是A1A2,判断是否有交点的线段是B1B2，则要求A1A2跨立B1B2。

设P1=向量(O->B1),P2=(O->B2),Q1=(O->A1),Q2=(O->A2);

则((P1-Q1)x(Q2-Q1))*((Q1-P2)x(Q2-Q1))>=0

 1 #include <iostream> 2 #include <cstring> 3 #include <algorithm> 4 #include <cstdio> 5 #include <math.h> 6 #define eps 0.00000001 7 using namespace std; 8  9 typedef struct po{10     double x,y;11 }Point;12 13 typedef struct pl{14     Point start,end;15 }Pleg;16 int how_point,how_pleg;17 Point pot[300];18 Pleg peg[300];19 Pleg Line;20 21 bool dbcmp(double x,double y){22     if(fabs(x-y)<eps) return false;23     return true;24 }25 26 double multi(Point a,Point b, Point c,Point d){27     return (a.x-b.x)*(c.y-d.y)-(a.y-b.y)*(c.x-d.x);28 }29 30 bool slove(int k){31     if(multi(peg[k].start,Line.start,Line.end,Line.start)*multi(Line.start,peg[k].end,Line.end,Line.start)>=0)32     return true;33     return false;34 }35 36 int main(){37     int T,n;38     scanf("%d",&T);39     while(T--){40         how_point=how_pleg=0;41         scanf("%d",&n);42         for(int i=1;i<=n;i++){43             scanf("%lf%lf",&pot[how_point].x,&pot[how_point].y);44             peg[how_pleg].start=pot[how_point];45             how_point++;46             scanf("%lf%lf",&pot[how_point].x,&pot[how_point].y);47             peg[how_pleg].end=pot[how_point];48             how_point++;49             how_pleg++;50         }51         bool flag=false;52         for(int i=0;i<how_point;i++){53             for(int j=i+1;j<how_point;j++){54                 if(!dbcmp(pot[i].x,pot[j].x)&&!dbcmp(pot[i].y,pot[j].y))55                 continue;56                 Line.start=pot[i]; Line.end=pot[j];57                 int k;58                 for(k=0;k<how_pleg;k++){59                     if(slove(k)){60                         continue;61                     }62                     break;63                 }64                 if(k==how_pleg){65                     flag=true;66                     break;67                 }68             }69             if(flag) break;70         }71         if(flag) printf("Yes!\n");72         else printf("No!\n");73     }74     return 0;75 }
View Code


联系
我们