好贷网好贷款

poj 3304 Segments(计算几何)

发布时间:2016-12-5 10:26:52 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"poj 3304 Segments(计算几何)",主要涉及到poj 3304 Segments(计算几何)方面的内容,对于poj 3304 Segments(计算几何)感兴趣的同学可以参考一下。

Segments Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 8246   Accepted: 2496 Description Given n segments in the two dimensional space, write a program, which determines if there exists a line such that after projecting these segments on it, all projected segments have at least one point in common. Input Input begins with a number T showing the number of test cases and then,T test cases follow. Each test case begins with a line containing a positive integern ≤ 100 showing the number of segments. After that, n lines containing four real numbersx1 y1 x2 y2 follow, in which (x1,y1) and (x2, y2) are the coordinates of the two endpoints for one of the segments. Output For each test case, your program must output "Yes!", if a line with desired property exists and must output "No!" otherwise. You must assume that two floating point numbersa and b are equal if |a - b| < 10-8. Sample Input 3 2 1.0 2.0 3.0 4.0 4.0 5.0 6.0 7.0 3 0.0 0.0 0.0 1.0 0.0 1.0 0.0 2.0 1.0 1.0 2.0 1.0 3 0.0 0.0 0.0 1.0 0.0 2.0 0.0 3.0 1.0 1.0 2.0 1.0 Sample Output Yes! Yes! No! Source Amirkabir University of Technology Local Contest 2006 题意:求是否存在这样的一条直线,直线上有一点被给出的所有直线在这条直线上的所有投影覆盖 题解:这等价于求一条过所有线段的直线是否存在,这也等价于枚举所有端点,是否能构成一条直线过所有线段 #include<stdio.h> #include<math.h> #define eps 1e-8 struct point{ double x,y; }p[203]; int n; double cross(struct point p1,struct point p2,struct point p3) { return (p2.x-p1.x)*(p3.y-p1.y)-(p2.y-p1.y)*(p3.x-p1.x); } int judge(struct point a,struct point b) { int i; if(sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y))<eps) return 0; for(i=0;i<n;i+=2) { if(cross(a,b,p[i])*cross(a,b,p[i+1])>eps) return 0; } return 1; } int jerry() { int i,j; for(i=0;i<n;i++) { for(j=i+1;j<n;j++) if(judge(p[i],p[j])) return 1; } return 0; } int main() { int t,i; scanf("%d",&t); while(t--) { scanf("%d",&n); n=n*2; for(i=0;i<n;i++) scanf("%lf%lf",&p[i].x,&p[i].y); if(jerry()) printf("Yes!\n"); else printf("No!\n"); } return 0; }

上一篇:极客技术专题【008期】:CSS3核心技术:选择器
下一篇:ADB server didn't ACK

相关文章

相关评论