Segments
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 x1 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 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!
Source
Amirkabir University of Technology Local Contest 2006
题目类型：直线与线段相交
算法分析：首先若存在一条直线使得所有线段在该直线上的投影都至少有一个交点的话，从这个相交的区域向各个线段做垂线与各线段都相交，所以本题其实求解的是是否存在一个与所有线段都相交的直线。由于直线与一组线段相交的话，可以通过平移和旋转在保证直线仍与所有线段相交时恰好通过所有线段的某两个端点，即若存在一条直线与所有线段相交，则该直线必定经过这些线段的某两个端点，所以枚举线段的端点构造直线并判断即可，注意若枚举到相同点时要跳过
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 |
/************************************************* Author :supermaker Created Time :2016/1/25 22:33:55 File Location :C:\Users\abcd\Desktop\TheEternalPoet **************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7F7F7F7F; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 166 + 66; int sgn (double val) { if (fabs (val) < EPS) return 0; else if (val < 0) return -1; else return 1; } struct Point { double x, y; Point () {} Point (double xx, double yy) : x (xx), y (yy) {} Point operator + (const Point &a) const { return Point (x + a.x, y + a.y); } Point operator - (const Point &a) const { return Point (x - a.x, y - a.y); } double operator ^ (const Point &a) const { return x * a.y - y * a.x; } double operator * (const Point &a) const { return x * a.x + y * a.y; } }; struct Line { Point s, e; Line () {} Line (Point ss, Point ee) : s (ss), e (ee) {} }; Line line[maxn]; int n; bool SegInerLine (Line l1, Line l2) { return sgn ((l2.s - l1.e) ^ (l1.s - l1.e)) * sgn ((l2.e - l1.e) ^ (l1.s - l1.e)) <= 0; } bool check (Point a, Point b) { if (sgn (a.x - b.x) == 0 && sgn (a.y - b.y) == 0) return false; Line tt = Line (a, b); for (int i = 1; i <= n; i++) if (!SegInerLine (tt, line[i])) return false; return true; } int main() { //CFF; //CPPFF; int t; scanf ("%d", &t); while (t--) { scanf ("%d", &n); for (int i = 1; i <= n; i++) { double x1, y1, x2, y2; scanf ("%lf%lf%lf%lf", &x1, &y1, &x2, &y2); line[i] = Line (Point (x1, y1), Point (x2, y2)); } bool is_have = false; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) { if (check (line[i].s, line[j].s) || check (line[i].s, line[j].e) || check (line[i].e, line[j].s) || check (line[i].e, line[j].e)) { is_have = true; break; } } if (is_have) puts ("Yes!"); else puts ("No!"); } return 0; } |
- hdu1392：下一篇 »