Segment
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 integer n ≤ 100 showing the number of segments. After that, n lines containing four real numbers x1y1x2y2 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 numbers a 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!
# include <iostream> # include <cmath> # include <cstdio> using namespace std; # define EPS 1e-8 int n; struct Segment { double x1,x2,y1,y2; }segment[1000]; double distance(double x1,double y1,double x2,double y2) { return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)); } double fun(double x1,double y1,double x2,double y2,double x0,double y0) { return (x2-x1)*(y0-y1)-(x0-x1)*(y2-y1); } bool search(double x1,double y1,double x2,double y2) { int i; //推断是不是同一条直线; if(distance(x1,y1,x2,y2)<EPS) return false; //利用叉积定理。推断是不是和其它的线段相交: for(i=0;i<n;i++) { if(fun(x1,y1,x2,y2,segment[i].x1,segment[i].y1)* fun(x1,y1,x2,y2,segment[i].x2,segment[i].y2)>EPS) return false; } return true; } int main () { //freopen("a.txt","r",stdin); int t; scanf("%d",&t); while(t--) { scanf("%d",&n); int i; for(i=0;i<n;i++) scanf("%lf%lf%lf%lf",&segment[i].x1,&segment[i].y1,&segment[i].x2,&segment[i].y2); if(n==1) { printf("Yes!\n"); continue;} int ans=0; //将全部的线段都列举出来。 for(i=0;i<n;i++) for(int j=i+1;j<n;j++) { if(search(segment[i].x1,segment[i].y1,segment[j].x1,segment[j].y1)|| search(segment[i].x1,segment[i].y1,segment[j].x2,segment[j].y2)|| search(segment[i].x2,segment[i].y2,segment[j].x1,segment[j].y1)|| search(segment[i].x2,segment[i].y2,segment[j].x2,segment[j].y2)) ans=1; } if(ans) printf("Yes!\n"); else printf("No!\n"); } return 0; }
相关文章
- Lintcode: Segment Tree Query II
- Lintcode: Segment Tree Modify
- Lintcode: Segment Tree Query
- Lintcode: Segment Tree Build
- Leetcode: Range Sum Query - Mutable && Summary: Segment Tree
- 【BZOJ3165】[HEOI2013]Segment(李超线段树)
- 线段树+离散化 IP地址段检查 SEGMENT TREE
- hdu5372 Segment Game
- BZOJ3165 : [Heoi2013]Segment
- 2015 Multi-University Training Contest 7 hdu 5372 Segment Game
- XTUOJ 1238 Segment Tree
- 131 Kafka Partition Segment
- Failed to complete obtain psql count Master gp_segment_configuration Script Exiti
- 《操作系统真象还原》——0.21 Section和Segment的区别
- 美团Leaf分布式ID Leaf安装和使用,美团Leaf snowflake雪花算法模式,美团Leaf segment号段模式
- 进程加载与segment
- ELF文件中section与segment的区别
- segment and section for c++ elf
- flanneld启动报错Failed to create SubnetManager: parse first path segment in URL cannot contain colon
- 分段树(segment tree)的实现 —— 强化学习中 "优先级回放机制" 的重要组成部分
- 【CodeForces 616D】Longest k-Good Segment
- Elasticsearch搜索引擎:ES的segment段合并原理
- CF242E XOR on Segment
- 线段树(Segment Tree)(转)
- HDU 5372 Segment Game
- [LintCode] Segment Tree Build II 建立线段树之二
- [LintCode] Segment Tree Build 建立线段树
- Segment Tree Range Minimum Query.