原题传送：http://poj.org/problem?id=1066
不用管“门要在墙壁中央”这个条件，直接枚举每个分割区间的中点为进入点，然后再求该进入点与藏宝点的线段与所有线段的最少交点数（不管路线怎么折，这个贪心策略都是正确的）。注意n=0的情况，注意线段相交精度（去除在端点相交的情况）。
View Code
1 #include <stdio.h> 2 #include <string.h> 3 #include <algorithm> 4 #include <vector> 5 #define eps 1e-10 6 using namespace std; 7 8 struct point 9 { 10 double x, y; 11 point(){} 12 point(double _x, double _y){x = _x; y = _y;} 13 }seg[35][2]; 14 15 int n; 16 double ex, ey; 17 vector<double> vl, vr, vu, vd; // 四个边缘墙壁 18 19 double min(double a, double b){return a < b ? a : b;} 20 double max(double a, double b){return a > b ? a : b; 21 } 22 bool inter(point a, point b, point c, point d) 23 { 24 if ( min(a.x, b.x) > max(c.x, d.x) || 25 min(a.y, b.y) > max(c.y, d.y) || 26 min(c.x, d.x) > max(a.x, b.x) || 27 min(c.y, d.y) > max(a.y, b.y) ) return 0; 28 double h, i, j, k; 29 h = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x); 30 i = (b.x - a.x) * (d.y - a.y) - (b.y - a.y) * (d.x - a.x); 31 j = (d.x - c.x) * (a.y - c.y) - (d.y - c.y) * (a.x - c.x); 32 k = (d.x - c.x) * (b.y - c.y) - (d.y - c.y) * (b.x - c.x); 33 return h * i < 0.0 && j * k < 0.0; // 相交点在端点的情况不能要 34 } 35 36 int cross(double x, double y) 37 { 38 int i, cnt; 39 for(cnt = i = 0; i < n; i ++) 40 if(inter(point(x, y), point(ex, ey), seg[i][0], seg[i][1])) 41 cnt ++; 42 return cnt; 43 } 44 45 int main() 46 { 47 int i, ans; 48 scanf("%d", &n); 49 for(i = 0; i < n; i ++) 50 { 51 scanf("%lf%lf%lf%lf", &seg[i][0].x, &seg[i][0].y, &seg[i][1].x, &seg[i][1].y); 52 if(seg[i][0].x < eps) 53 vl.push_back(seg[i][0].y); 54 else if(seg[i][0].x - 100.0 < eps) 55 vr.push_back(seg[i][0].y); 56 57 if(seg[i][0].y < eps) 58 vd.push_back(seg[i][0].x); 59 else if(seg[i][0].x - 100.0 < eps) 60 vu.push_back(seg[i][0].x); 61 62 if(seg[i][1].x < eps) 63 vl.push_back(seg[i][1].y); 64 else if(seg[i][1].x - 100.0 < eps) 65 vr.push_back(seg[i][1].y); 66 67 if(seg[i][1].y < eps) 68 vd.push_back(seg[i][1].x); 69 else if(seg[i][1].x - 100.0 < eps) 70 vu.push_back(seg[i][1].x); 71 } 72 scanf("%lf%lf", &ex, &ey); 73 if(n == 0) 74 { 75 printf("Number of doors = 1\n"); 76 return 0; 77 } 78 sort(vl.begin(), vl.end()); 79 sort(vr.begin(), vr.end()); 80 sort(vd.begin(), vd.end()); 81 sort(vu.begin(), vu.end()); 82 ans = 100000000; 83 for(i = 0; i < vl.size(); i ++) 84 { 85 int tmp = cross(0.0, i == 0 ? (vl[0] / 2) : (vl[i] + vl[i - 1]) / 2); 86 ans = min(ans, tmp); 87 } 88 for(i = 0; i < vr.size(); i ++) 89 { 90 int tmp = cross(100.0, i == 0 ? (vr[0] / 2) : (vr[i] + vr[i - 1]) / 2); 91 ans = min(ans, tmp); 92 } 93 for(i = 0; i < vu.size(); i ++) 94 { 95 int tmp = cross(i == 0 ? (vu[0] / 2) : (vu[i] + vu[i - 1]) / 2, 100.0); 96 ans = min(ans, tmp); 97 } 98 for(i = 0; i < vd.size(); i ++) 99 { 100 int tmp = cross(i == 0 ? (vd[0] / 2) : (vd[i] + vd[i - 1]) / 2, 0.0); 101 ans = min(ans, tmp); 102 } 103 printf("Number of doors = %d\n", ans + 1); 104 return 0; 105 } 106