题目链接：http://poj.org/PRoblem?id=3304 题意:给你n条线段，让你找一条线段使得这n条线段在上面的投影至少有一个交点 解析：画个图就知道，如果有一条线段与n条线段全部相交，那么这条线段的垂线就能满足题意要求，把这条直线稍微转一下，总能使得，这条线的端点是n条直线的两个端点，于是只需要枚举每个端点，然后进行判断即可。
#include <cmath>#include <algorithm>#include <iostream>#include <cstdio>#include <vector>#include <cstring>#include <stack>using namespace std;const int maxn = 105+100;const double eps = 1e-8;int n;struct point{ double x,y; point() {} point(double _x,double _y) { x = _x; y = _y; }};struct line{ point a; point b;}a[maxn];double dis(point p0,point p1){ return sqrt((p0.x-p1.x)*(p0.x-p1.x)+(p0.y-p1.y)*(p0.y-p1.y));}double x_mul(point p0,point p1,point p2){ return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);}bool judge(point t1,point t2){ if(dis(t1,t2)<eps) return false; for(int i=0;i<n;i++) { if((x_mul(a[i].a,t1,t2)*x_mul(a[i].b,t1,t2)>eps)) return false; } return true;}int main(void){ int t; cin>>t; while(t--) { scanf("%d",&n); for(int i=0;i<n;i++) { point t1,t2; scanf("%lf %lf %lf %lf",&t1.x,&t1.y,&t2.x,&t2.y); a[i].a = t1; a[i].b = t2; } if(n==1) { puts("Yes!"); continue; } int flag = 0; for(int i=0;i<n;i++) { for(int j=i+1;j<n;j++) { if(judge(a[i].a,a[j].b)|| judge(a[i].a,a[j].a)|| judge(a[i].b,a[j].b)|| judge(a[i].b,a[j].a)) { flag = 1; break; } } if(flag) break; } if(flag) puts("Yes!"); else puts("No!"); } return 0;}新闻热点
疑难解答
