大概思路:若存在一条直线l和所有线段相交,作一条直线m和l垂直,则m就是题中要求的直线,所有线段投影的一个公共点即为垂足。即把问题转化成求是否存在一条直线与每条线段都有交点。这里用到枚举,枚举两两线段的各一个端点,连一条直线,再判断剩下的线段是否都和这条直线有交点。
判断线段与直线l是否相交的方法:利用叉积的性质,判断线段的两个端点是否在直线的两边。
本题需要注意两点:
1.需要考虑当n=1的情况,当然n=1和2都是Yes。
2.在枚举所有顶点的时候考虑一下顶点的距离小于1.0*10^(-8)时是不用考虑的。
具体代码实现:
#include <iostream> #include <cmath> using namespace std; const int Max=105; const double eps=1e-8; struct point { double x ,y ; }; struct line { point a ,b ; }s[Max]; double mult (point p1 ,point p2 ,point p0){ return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y); } bool judgement (point p1 ,point p2 ,int n){ if(abs(p1.x-p2.x) < eps && abs(p1.y-p2.y) < eps) return false; for (int i=0 ;i<n ;i++){ if(mult(p1 ,p2 ,s[i].a)*mult(p1 ,p2 ,s[i].b)>eps) return false; } return true; } int main() { int t ; cin >>t ; while(t--){ int n ,i ,j ; cin >>n ; for (i=0 ;i<n ;i++){ cin >>s[i].a.x>>s[i].a.y>>s[i].b.x>>s[i].b.y ; } bool flag=false ; if (n<3) flag=true ; for (i=0 ;i<n&&!flag ;i++){ for (j=i+1 ;j<n&&!flag ;j++){ if(judgement(s[i].a,s[j].a,n)) flag=true; else if (judgement(s[i].a,s[j].b,n)) flag=true; else if (judgement(s[i].b,s[j].a,n)) flag=true; else if (judgement(s[i].b,s[j].b,n)) flag=true; } } if(flag) cout <<"Yes!"<<endl; else cout <<"No!"<<endl; } return 0; }
版权声明:本文为博主原创文章,未经博主允许不得转载。