2009年12月6日星期日.sgu124
sgu124:判斷點(diǎn)在多邊形內(nèi)還是外還是邊上
由于線段是隨機(jī)給出的，沒有順時針或者逆時針順序，所以轉(zhuǎn)角法是不能用的
主要考慮射線法
射線法可以參考黑數(shù)P379,有詳細(xì)的講解，也很好理解
trick
1.要注意平行線段的處理，其實(shí)出現(xiàn)射線穿過線段端點(diǎn)的情況，完全和可以忽略
2.判斷線段和射線相交時，要注意判斷交點(diǎn)是不是在射線上也就是
對于射線L:P0 + s*v ,(s >= 0) 要注意判斷交點(diǎn)在s >= 0時才算相交
其他就沒有了。
做sgu的題真鍛煉，已經(jīng)很久沒期待過1Y了...
1
2 /*
3 * SOUR:sgu124
4 * ALGO:computational geometry
5 * DATE: 2009年 12月 06日 星期日 20:50:13 CST
6 * COMM:3
7 * */
8 #include<iostream>
9 #include<cstdio>
10 #include<cstdlib>
11 #include<cstring>
12 #include<algorithm>
13 using namespace std;
14 typedef long long LL;
15 const int maxint = 0x7fffffff;
16 const long long max64 = 0x7fffffffffffffffll;
17
18 const int N = 10100;
19 const double eps = 1e-10;
20 int dcmp(double x) { return (x > eps) - (x < -eps);}
21 struct point_t {
22 double x, y;
23 point_t (){}
24 point_t (double a,double b){x = a,y = b;}
25 }p[N][2],core;
26 point_t operator + (point_t a,point_t b) { return point_t(a.x + b.x,a.y + b.y);}
27 point_t operator - (point_t a,point_t b) { return point_t(a.x - b.x,a.y - b.y);}
28 double dot_mul(point_t a,point_t b) { return a.x * b.x + a.y * b.y;}
29 double cross_mul(point_t a,point_t b) { return a.x * b.y - a.y * b.x;}
30 double cross_mul(point_t a,point_t b,point_t c) { return cross_mul(a-c,b-c);}
31 double dist2(point_t a,point_t b) { return (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y);}
32
33 bool judge(point_t a,point_t b,point_t c,point_t d)
34 {
35 if(dcmp(cross_mul(a-c,d-c)) * dcmp(cross_mul(b-c,d-c)) < 0) {
36 if(dcmp(cross_mul(a-b,c-b)) > 0) //射線端
37 return true;
38 }
39 return false;
40 }
41
42 int n;
43 bool rel(point_t a,point_t b,point_t c)
44 //a 和線段bc
45 {
46 double tmp =(dot_mul(a-b,c-b) / dist2(b,c)) ;
47 //printf("rel = %f\n",tmp);
48 return tmp >= 0 && tmp <= 1;
49 }
50
51 void work()
52 {
53 int sum = 0;
54 point_t to = core;
55 to.x += 1;//隨便取的射線
56 to.y += 7;
57 for(int i = 0;i < n ;i++) {
58 if(0 == dcmp(cross_mul(p[i][1] - p[i][0],core-p[i][0])) &&
59 rel(core,p[i][0],p[i][1])) {
60 printf("BORDER\n");
61 return;
62 }
63 if(judge(p[i][0],p[i][1],core,to))
64 sum++;
65 }
66 //printf("sum=%d\n",sum);
67 if(sum & 1) {
68 printf("INSIDE\n");
69 }else {
70 printf("OUTSIDE\n");
71 }
72 }
73
74 int main()
75 {
76 int i,j,k;
77 scanf("%d",&n);
78 for(i = 0;i < n;i++) {
79 scanf("%lf%lf%lf%lf",&p[i][0].x,&p[i][0].y,&p[i][1].x,&p[i][1].y);
80
81 if(p[i][0].y < p[i][1].y) { //保證線段總是指向左上的
82 swap(p[i][0],p[i][1]);
83 }else if(p[i][0].y == p[i][1].y && p[i][0].x > p[i][1].x) {
84 swap(p[i][0],p[i][1]);
85 }
86 }
87 scanf("%lf%lf",&core.x,&core.y);
88 work();
89 return 0;
90 }
91
92