2010年1月24日星期日.sgu129
sgu129:其實(shí)不難，求線段在凸多邊形中的長(zhǎng)度
雖然是基礎(chǔ)計(jì)算幾何問(wèn)題，但是請(qǐng)看題目通過(guò)人數(shù):
129 Inheritance 357 +
在第一頁(yè)最前邊，才這么點(diǎn)人過(guò)，說(shuō)明這道題很有點(diǎn)意思。
我也看了網(wǎng)上很多人的解題報(bào)告，幾乎眾口一辭的說(shuō)是精度問(wèn)題，但是我不同意。
首先題目中已經(jīng)說(shuō)了都是整點(diǎn)，所以，完全可以利用整數(shù)的性質(zhì)回避掉精度的問(wèn)題。
double proc()
{
如果線段和一條凸包的邊所在的直線重合，return 0;
如果凸包的端點(diǎn)在這條線段上，p[cnt++] = intersect_point;
如果凸包的一條線段和這條線段相交，且交點(diǎn)不是凸包先端的端點(diǎn)，
p[cnt++] = intersect_point;
if(cnt == 0) { //全內(nèi)或全外
if (inPoly(a) && inPoly(b)) { return dist(a,b); }
}else if (cnt == 1) { //一個(gè)交點(diǎn),此種情況也可能為0
if (inPoly(a)) { return dist(a,p[0]); }
if (inPoly(b)) { return dist(b,p[0]); }
}else {
return dist(p[0],p[1]);
}
return 0;
}
最丑的第一次ac的代碼就不貼了，貼一下很"靚"的沒(méi)有用dcmp的代碼
1
2 /*
3 * SOUR:sgu129
4 * ALGO:computational geometry
5 * DATE: 2010年 01月 20日 星期三 22:24:30 CST
6 * COMM:5 http://m.shnenglu.com/schindlerlee
7 * 其實(shí)都是整點(diǎn)，精度控制可以完全不用dcmp
8 * */
9 #include<iostream>
10 #include<cstdio>
11 #include<cstdlib>
12 #include<cstring>
13 #include<algorithm>
14 #include<cmath>
15 using namespace std;
16 typedef long long LL;
17 const int maxint = 0x7fffffff;
18 const long long max64 = 0x7fffffffffffffffll;
19
20 const int N = 1024;
21 struct point_t {
22 double x, y;
23 point_t() {
24 } point_t(double a, double b) {
25 x = a, y = b;
26 }
27 } p[N], st[N],line[2];
28
29 double sqr(double x) { return x * x;}
30 point_t operator +(point_t a, point_t b) { return point_t(a.x + b.x, a.y + b.y); }
31 point_t operator -(point_t a, point_t b) { return point_t(a.x - b.x, a.y - b.y); }
32 double dot_mul(point_t a, point_t b) { return a.x * b.x + a.y * b.y; }
33 double cross_mul(point_t a, point_t b) { return a.x * b.y - a.y * b.x; }
34 double cross_mul(point_t a, point_t b, point_t c) { return cross_mul(a - c, b - c); }
35
36 double dist(double ax,double ay,double bx,double by) { return sqrt(sqr(ax-bx) + sqr(ay-by));}
37 double dist(point_t a) { return sqrt(sqr(a.x) + sqr(a.y));}
38 double dist(point_t a,point_t b) { return dist(a-b);}
39 int m, n, top;
40 bool cmp(point_t a, point_t b) { return cross_mul(a, b, p[0]) > 0; }
41
42 void graham()
43 {
44 int i;
45 top = 0;
46 for (i = 1; i < n; i++) {
47 if (p[i].y < p[0].y) {
48 swap(p[i], p[0]);
49 } else if (p[i].y == p[0].y && p[i].x < p[0].x) {
50 swap(p[i], p[0]);
51 }
52 }
53 sort(p + 1, p + n, cmp);
54 st[0] = p[0];
55 st[1] = p[1];
56 top = 2;
57 for (i = 2; i < n; i++) {
58 if (cross_mul(p[i], st[top - 1], st[top - 2]) <= 0) {
59 st[top++] = p[i];
60 } else {
61 top--;
62 }
63 }
64 st[top++] = st[0];
65 }
66
67 bool inPoly (point_t pt)
68 {
69 for (int i = 0;i < top - 1;i++) {
70 point_t a = st[i];
71 point_t b = st[i+1];
72 if (cross_mul(b,pt,a) <= 0) {
73 return false;
74 }
75 }
76 return true;
77 }
78
79 bool between(point_t a,point_t bg,point_t ed)
80 {
81 if (a.x >= min(bg.x,ed.x) && a.x <= max(bg.x,ed.x) &&
82 a.y >= min(bg.y,ed.y) && a.y <= max(bg.y,ed.y)) {
83 return 1;
84 }
85 return 0;
86 }
87
88 bool onSeg(point_t a,point_t b,point_t c) //a is on bc
89 {
90 if(0 == cross_mul(a,b,c)) {
91 if(between(a,b,c)) {
92 return true;
93 } else {
94 return false;
95 }
96 }
97 return false;
98 }
99
100 bool intersect(point_t a,point_t b,point_t c,point_t d,double &x,double &y)
101 {
102 double r1,r2;
103 if (cross_mul(a,c,d) * cross_mul(b,c,d) < 0 &&
104 (r1=cross_mul(c,a,b)) * (r2=cross_mul(d,a,b)) <= 0) { //!! 注意是 <= 0
105 r1 = fabs(r1), r2 = fabs(r2);
106 x = c.x + (d.x - c.x) * (r1/(r1+r2));
107 y = c.y + (d.y - c.y) * (r1/(r1+r2));
108 return true;
109 }
110 return false;
111 }
112
113 double proc(point_t bg,point_t ed)
114 {
115 int i,j;
116 for (i = 0;i < top - 1;i ++) {
117 point_t a = st[i];
118 point_t b = st[i+1];
119 if(cross_mul(a,bg,b) == 0 && cross_mul(a,ed,b) == 0) //在一條直線上
120 return 0;
121 }
122 double x[2],y[2],tx,ty;
123 int cnt = 0;
124
125 for (i = 0;i < top - 1;i++) {
126 point_t a = st[i];
127 //if (cross_mul(bg,a,ed) == 0 && between(a,bg,ed)) {
128 if (onSeg(a,bg,ed)) {
129 x[cnt] = a.x, y[cnt] = a.y, cnt++;
130 }
131 }
132
133 for (i = 0;i < top - 1;i++) {
134 point_t a = st[i];
135 point_t b = st[i+1];
136 if (intersect(a,b,bg,ed,tx,ty)) {
137 x[cnt] = tx, y[cnt] = ty, cnt++;
138 }
139 }
140 if (cnt == 0) {
141 if (inPoly(bg) && inPoly(ed)) {
142 return dist(bg,ed);
143 }
144 }else if (cnt == 1) {
145 if (inPoly(bg)) { return dist(x[0],y[0],bg.x,bg.y); }
146 if (inPoly(ed)) { return dist(x[0],y[0],ed.x,ed.y); }
147 }else if (cnt == 2) {
148 return dist(x[0],y[0],x[1],y[1]);
149 }
150 return 0;
151 }
152
153 int main()
154 {
155 int i, j, k;
156 scanf("%d", &n);
157 for (i = 0; i < n; i++) {
158 scanf("%lf%lf", &p[i].x, &p[i].y);
159 }
160 graham();
161
162 scanf("%d", &m);
163 while (m--) {
164 scanf("%lf%lf",&line[0].x,&line[0].y);
165 scanf("%lf%lf",&line[1].x,&line[1].y);
166 printf("%f\n",proc(line[0],line[1]));
167 }
168 return 0;
169 }
170