Treasure Hunt
Archeologists from the Antiquities and Curios Museum (ACM) have flown to Egypt to examine the great pyramid of Key-Ops. Using state-of-the-art technology they are able to determine that the lower floor of the pyramid is constructed from a series of straightline walls, which intersect to form numerous enclosed chambers. Currently, no doors exist to allow access to any chamber. This state-of-the-art technology has also pinpointed the location of the treasure room. What these dedicated (and greedy) archeologists want to do is blast doors through the walls to get to the treasure room. However, to minimize the damage to the artwork in the intervening chambers (and stay under their government grant for dynamite) they want to blast through the minimum number of doors. For structural integrity purposes, doors should only be blasted at the midpoint of the wall of the room being entered. You are to write a program which determines this minimum number of doors.
An example is shown below:
Input
The input will consist of one case. The first line will be an integer n (0 <= n <= 30) specifying number of interior walls, followed by n lines containing integer endpoints of each wall x1 y1 x2 y2 . The 4 enclosing walls of the pyramid have fixed endpoints at (0,0); (0,100); (100,100) and (100,0) and are not included in the list of walls. The interior walls always span from one exterior wall to another exterior wall and are arranged such that no more than two walls intersect at any point. You may assume that no two given walls coincide. After the listing of the interior walls there will be one final line containing the floating point coordinates of the treasure in the treasure room (guaranteed not to lie on a wall).
Output
Print a single line listing the minimum number of doors which need to be created, in the format shown below.
Sample Input
7
20 0 37 100
40 0 76 100
85 0 0 75
100 90 0 90
0 71 100 61
0 14 100 38
100 47 47 100
54.5 55.4
Sample Output
Number of doors = 2
Source
East Central North America 1999
题目类型：线段相交+构造
算法分析：由于内部的线段是从外墙的一个边到另一个边的，所以若从外墙的某一个点开始找宝物一定会遇到k个墙的话，则最少会炸k个墙。所以可以枚举外墙上的每个点与宝物位置构造线段，然后判断与剩下的线段相交的交点数，取最少的即可。一个简单优化是内墙与外墙的交点是最少满足条件的点，所以可以直接枚举内墙的端点和外墙的4个端点而不用枚举外墙上的所有点
|
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 148 149 150 |
/************************************************* Author :supermaker Created Time :2016/1/30 13:32:18 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 = 66; int sgn (double val) { if (fabs (val) < EPS) return 0; else if (val < 0) return -1; 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); } 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) {} }; bool Inter (Line l1, Line l2) { return max (l1.s.x, l1.e.x) >= min (l2.s.x, l2.e.x) && max (l2.s.x, l2.e.x) >= min (l1.s.x, l1.e.x) && max (l1.s.y, l1.e.y) >= min (l2.s.y, l2.e.y) && max (l2.s.y, l2.e.y) >= min (l1.s.y, l1.e.y) && sgn ((l2.s - l1.e) ^ (l1.s - l1.e)) * sgn ((l2.e - l1.e) ^ (l1.s - l1.e) ) <= 0 && sgn ((l1.s - l2.e) ^ (l2.s - l2.e)) * sgn ((l1.e - l2.e) ^ (l2.s - l2.e))<= 0; } int n; Point p[maxn*2], pp[6] = {Point (0, 0), Point (0, 100), Point (100, 0), Point (100, 100)}; Line l[maxn]; int main() { //CFF; //CPPFF; while (scanf ("%d", &n) != EOF) { for (int i = 1; i <= n; i++) { double x1, y1, x2, y2; scanf ("%lf%lf%lf%lf", &x1, &y1, &x2, &y2); l[i] = Line (Point (x1, y1), Point (x2, y2)); p[i*2-1] = Point (x1, y1); p[i*2] = Point (x2, y2); } double x0, y0; scanf ("%lf%lf", &x0, &y0); Point e = Point (x0, y0); int res = INF; for (int i = 1; i <= 2 * n; i++) { Line tt = Line (e, p[i]); int cnt = 0; for (int j = 1; j <= n; j++) if (Inter (tt, l[j])) cnt++; res = min (res, cnt); } for (int i = 1; i <= 4; i++) { Line tt = Line (e, pp[i]); int cnt = 0; for (int j = 1; j <= n; j++) if (Inter (tt, l[j])) cnt++; res = min (res, cnt + 1); } printf ("Number of doors = %d\n", res); } return 0; } |