首页 > 代码库 > POJ 3304 Segments （直线与线段是否相交）
POJ 3304 Segments （直线与线段是否相交）
题目链接
题意 ： 能否找出一条直线使得所有给定的线段在该直线上的投影有一个公共点。
思路 ： 假设存在一条直线a使得所有线段在该直线上的投影有公共点，则必存在一条垂直于直线a的直线b，直线b与所有线段相交，所以问题又转变为是否存在一条直线与所在所有线段相交。
假设这样的直线存在，则这一条直线可能与某一条或者某些线段的端点重合，也可能不重合。对于那些没有在端点相交的线段，我们可以把这一条直线通过旋转或平移，让其先与一条线段在线段的端点相交(那此时这一条直线与别的线段就在别的线段的中间相交)， 然后继续旋转，让这一条直线与别的直线也在端点处相交。到此为止，我们可以明白所有存在的这样的直线都可以这样平移和旋转来处理他。那么反过来，如果我们用所有的线段的端点(任意组合)构成的直线都不满足和所有的线段至少有一个公共点，也就是说不存在这样的直线。
要注意的是小于1e-8就算是重点，所以要注意判断
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <cmath> 5 #include <algorithm> 6 #define eps 1e-8 7 8 using namespace std ; 9 10 struct point11 {12 double x,y;13 }p[210];14 struct line15 {16 point a,b;17 }L[110];18 19 double multi(point a,point b,point c)20 {21 return ((a.x-c.x)*(b.y-c.y) - (b.x-c.x)*(a.y-c.y)) ;22 }23 bool inter(line L,point a,point b)24 {25 double x1 = multi(L.a,a,b) ;26 double x2 = multi(L.b,a,b) ;27 if((x1 > eps && x2 < -eps) || (x1 < -eps && x2 > eps) || (fabs(x1) < eps) || (fabs(x2) < eps))28 return true ;29 return false ;30 }31 int main()32 {33 int T ,n;34 scanf("%d",&T) ;35 while(T--)36 {37 scanf("%d",&n) ;38 int cnt = 0 ;39 for(int i = 0 ; i < n ; i++)40 {41 scanf("%lf %lf %lf %lf",&L[i].a.x,&L[i].a.y,&L[i].b.x,&L[i].b.y) ;42 p[cnt ++] = L[i].a ;43 p[cnt ++] = L[i].b ;44 // printf("2\n") ;45 }46 //printf("1\n") ;47 bool ans = false ;48 for(int i = 0 ; i < cnt-1 ; i++)49 {50 for(int j = i+1 ; j < cnt ; j++)51 {52 if(fabs(p[i].x-p[j].x) < eps && fabs(p[i].y-p[j].y) < eps) continue ;53 bool flag = true ;54 for(int k = 0 ; k < n ; k++)55 {56 if(!inter(L[k],p[i],p[j]))57 {58 flag = false ;59 break ;60 }61 }62 if(flag)63 {64 ans = true ;65 break ;66 }67 }68 }69 if(ans) puts("Yes!") ;70 else puts("No!") ;71 }72 return 0 ;73 }
POJ 3304 Segments （直线与线段是否相交）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。