Posted on 2008-09-02 20:09
Hero 閱讀(259)
評論(0) 編輯 收藏 引用 所屬分類:
代碼如詩－－ACM
1 //Accepted 1120 C++ 0.02s 190K 054100526 FZU
2
3 //點(diǎn)在多邊形內(nèi)
4 //不滿足 z=px+qy 的個(gè)數(shù)為(p-1)*(q-1)/2
5
6 #include <stdio.h>
7 #include <stdlib.h>
8 #include <string.h>
9
10 #define offset 10000
11 #define eps 1e-8
12 #define zero(x) (((x)>0?(x):-(x))<eps)
13 #define _sign(x) ((x)>eps?1:((x)<-eps?2:0))
14 const int INF = 99999999 ;
15 const int size = 20 ;
16
17 struct point
18 {
19 double x ;
20 double y ;
21 };
22 struct point pt[size] ;
23
24 double minx, miny ;
25 double maxx, maxy ;
26 int inn ; int inp, inq ; int ct ;
27
28 void input()
29 {
30 minx = miny = INF ; maxx = maxy = -1*INF ;
31 for( int i=0; i<inn; i++ )
32 {
33 scanf( "%lf %lf", &pt[i].x, &pt[i].y ) ;
34 //if( minx > pt[i].x ) minx = pt[i].x ;
35 //if( miny > pt[i].y ) miny = pt[i].y ;
36
37 //if( maxx < pt[i].x ) maxx = pt[i].x ;
38 //if( maxy < pt[i].x ) maxy = pt[i].y ;
39 }
40 }
41
42 double xmult(point p1,point p2,point p0){
43 return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
44 }
45
46 //判點(diǎn)在任意多邊形內(nèi),頂點(diǎn)按順時(shí)針或逆時(shí)針給出
47 //on_edge表示點(diǎn)在多邊形邊上時(shí)的返回值,offset為多邊形坐標(biāo)上限
48 int inside_polygon(point q,int n,point* p,int on_edge=1){
49 point q2;
50 int i=0,count;
51 while (i<n)
52 for (count=i=0,q2.x=rand()+offset,q2.y=rand()+offset;i<n;i++)
53 if (zero(xmult(q,p[i],p[(i+1)%n]))&&(p[i].x-q.x)*(p[(i+1)%n].x-q.x)<eps&&(p[i].y-q.y)*(p[(i+1)%n].y-q.y)<eps)
54 return on_edge;
55 else if (zero(xmult(q,q2,p[i])))
56 break;
57 else if (xmult(q,p[i],q2)*xmult(q,p[(i+1)%n],q2)<-eps&&xmult(p[i],q,p[(i+1)%n])*xmult(p[i],q2,p[(i+1)%n])<-eps)
58 count++;
59 return count&1;
60 }
61
62 void process()
63 {
64 scanf( "%d %d", &inp, &inq ) ;
65
66 struct point q ; q.x = 0.0 ; q.y = 0.0 ;
67
68 if( inside_polygon( q, inn, pt, 1 ) )
69 {
70 printf( "The pilot is in danger!\n" ) ;
71 printf( "The secret number is %d.\n", (inp-1)*(inq-1)/2 ) ;
72 }
73 else
74 {
75 printf( "The pilot is safe.\n" ) ;
76 }
77 printf( "\n" ) ;
78 }
79
80 int main()
81 {
82 //freopen( "in.txt", "r", stdin ) ;
83
84 ct = 1 ;
85 while( scanf( "%d", &inn ) != EOF && inn )
86 {
87 printf( "Pilot %d\n", ct++ ) ;
88
89 input() ;
90
91 process() ;
92
93 //output() ;
94 }
95
96 return 0 ;
97 }