随笔-21  评论-10  文章-21  trackbacks-0

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(00);
37     P[cnt++= Point(1000);
38     P[cnt++= Point(0100);
39     P[cnt++= Point(100100);
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 阅读(562) 评论(5)  编辑 收藏 引用 所属分类: geometry

评论:
# re: pku 1066 Treasure Hunt[未登录] 2009-09-03 13:42 | SImon
博主我想请问一下
如果我枚举分块的两个端点,这样应该也可以吧?  回复  更多评论
  
# re: pku 1066 Treasure Hunt[未登录] 2009-09-03 13:43 | SImon
我还想请问一个问题
你判断相交的时候为什么不需要快速排斥原理呢?  回复  更多评论
  
# re: pku 1066 Treasure Hunt 2009-09-03 19:01 | logics_space

判断同异侧要避免点在线段上的情况

之所以不要线段相交里的快速排斥原理,见原题的这句话
The interior walls always span from one exterior wall to another exterior wall  回复  更多评论
  
# re: pku 1066 Treasure Hunt[未登录] 2009-09-03 19:49 | SImon
@logics_space
或许是我对判线段相交不大理解
大牛能解释一下判断线段相交的时候为什么要先用排斥原理呢?
有什么是能通过跨越原理但是通不过排斥原理的吗?

谢谢大牛解惑~  回复  更多评论
  
# re: pku 1066 Treasure Hunt 2009-09-03 20:32 | logics_space
并不是一定要先用排斥原理,也可以不用,
如果你说的是严格的跨立,那通过跨立原理的必相交,必通过着排斥原理
如果是非严格的跨立(叉积可以==0)比如(0,0) (1,1) 和(4,4)(5,3)能过非严格的跨立,但过不了排斥
但(4,0)(0,4)和(3,4)(6,-2)能过排斥,也能过非严格的跨立  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理