PKU
1066 是一道感觉很好的题，用同侧异侧（位置）来表示的话思路会很清晰。
首先要从起点到终点穿过一道墙，等价于起点和终点在墙的异侧，这样就清楚的表示了穿过一道墙的充要条件。
接下来也变得简单，就是枚举终点，终点显然在正方形的边上。很快能发现他们是一块一块的。紧邻的交点（墙和正方形所交的点）所构成的线段上的点相对墙的位置是同侧。因为他们没有被任何墙分割开。也就不可能异侧。
这样只要分块枚举，一块枚举只需一个点。
1 #include<iostream>
2 #include<cmath>
3 #include<algorithm>
4 using namespace std;
5 double const EPS = 1e-8;
6 const int INF = 1<<30;
7
8 int dcmp(double x){return x < -EPS ? -1 : x > EPS;}
9
10 struct Point{
11 double x,y;
12 Point(){}
13 Point(double a, double b):x(a), y(b){}
14 bool operator<(Point a){return atan2(y - 50, x - 50) < atan2(a.y - 50, a.x - 50); }
15 };
16
17 struct Line{Point a, b;};
18
19 Point P[128], s, t;
20 Line L[36];
21 int n, cnt, best;
22
23 double xmult(Point p1, Point p2 , Point p0)
24 {
25 return (p1.x - p0.x)*(p2.y - p0.y)-(p2.x - p0.x)*(p1.y - p0.y);
26 }
27 bool same_side(Point p1, Point p2, Line L)
28 {
29 return dcmp(xmult(L.b, p1, L.a) * xmult(L.b, p2, L.a)) >= 0;
30 }
31
32 int main()
33 {
34 int i, j, ans;
35 best = INF; cnt = 0;
36 P[cnt++] = Point(0, 0);
37 P[cnt++] = Point(100, 0);
38 P[cnt++] = Point(0, 100);
39 P[cnt++] = Point(100, 100);
40
41 cin >> n;
42 for(i = 0; i < n; i++)
43 {
44 cin>> L[i].a.x >> L[i].a.y >> L[i].b.x >> L[i].b.y;
45 P[cnt++] = L[i].a;
46 P[cnt++] = L[i].b;
47 }
48 cin>> s.x >> s.y;
49
50 sort(P, P+cnt);
51
52 for(i = 0; i < cnt; i++ )
53 {
54 ans = 0;
55 t = Point( (P[i].x + P[(i+1)%cnt].x)/2, (P[i].y + P[(i+1)%cnt].y)/2 );
56 for(j = 0; j < n; j++)
57 if(!same_side(s, t, L[j]))ans++;
58 if(ans < best) best = ans;
59 }
60
61 printf("Number of doors = %d\n", best+1);
62 }
posted on 2009-07-24 16:20
wangzhihao 阅读(573)
评论(5) 编辑 收藏 引用 所属分类:
geometry