4445: [Scoi2015]小凸想跑步
Time Limit: 2 Sec Memory Limit: 128 MBDescription
小凸晚上喜欢到操场跑步，今天他跑完两圈之后，他玩起了这样一个游戏。
操场是个凸n边形，N个顶点按照逆时针从0～n-l编号。现在小凸随机站在操场中的某个位置，标记为
P点。将P点与n个顶点各连一条边，形成N个三角形。如果这时P点，0号点，1号点形成的三角形的面
积是N个三角形中最小的一个，小凸则认为这是一次正确站位。
现在小凸想知道他一次站位正确的概率是多少。
Input
第1行包含1个整数n，表示操场的顶点数和游戏的次数。
接下来有N行，每行包含2个整数Xi,Yi表示顶点的坐标。
输入保证按逆时针顺序输入点，所有点保证构成一个n多边形。所有点保证不存在三点共线。
Output
输出1个数，正确站位的概率，保留4位小数。
Sample Input
5
1 8
0 7
0 0
8 0
8 8
1 8
0 7
0 0
8 0
8 8
Sample Output
0.6316
HINT
3<=N<=10^5,-10^9<=X,Y<=10^9
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <cmath> 6 #define LL long long 7 8 using namespace std; 9 10 const double eps = 1e-15; 11 const int MAXN = 2e5 + 10; 12 13 int N; 14 const double inf = 1e18; 15 int tot = 0; 16 double sum1 = 0, sum2 = 0; 17 int head = 0, tail = 0; 18 int s[MAXN]; 19 double x, y, xx, yy; 20 21 inline LL read() 22 { 23 LL x = 0, w = 1; char ch = 0; 24 while(ch < '0' || ch > '9') { 25 if(ch == '-') { 26 w = -1; 27 } 28 ch = getchar(); 29 } 30 while(ch >= '0' && ch <= '9') { 31 x = x * 10 + ch - '0'; 32 ch = getchar(); 33 } 34 return x * w; 35 } 36 37 38 int dcmp(double x) 39 { 40 if(x <= eps && x >= -eps) { 41 return 0; 42 } 43 if(x > 0) { 44 return 1; 45 } 46 return -1; 47 } 48 49 struct vector { 50 double x, y; 51 } p[MAXN], temp, n[MAXN]; 52 53 typedef vector point; 54 struct line { 55 double k, b; 56 double tan; 57 vector v; 58 point p; 59 double x1, y1; 60 double x2, y2; 61 } l[MAXN * 4]; 62 63 bool cmp(line a, line b) 64 { 65 return a.tan < b.tan; 66 } 67 68 69 /*Point GLI(Point P,Vector v,Point Q,Vector w) 70 { 71 Vector u=P-Q; 72 double t=Cross(w,u)/Cross(v,w); 73 return P+v*t; 74 }*/ 75 76 vector operator -(vector a, vector b) 77 { 78 vector temp; 79 temp.x = a.x - b.x, temp.y = a.y - b.y; 80 return temp; 81 } 82 83 vector operator +(vector a, vector b) 84 { 85 vector temp; 86 temp.x = a.x + b.x, temp.y = a.y + b.y; 87 return temp; 88 } 89 90 vector operator *(vector a, double b) 91 { 92 vector temp; 93 temp.x = a.x * b, temp.y = a.y * b; 94 return temp; 95 } 96 double cross(vector a, vector b) 97 { 98 return a.x * b.y - b.x * a.y; 99 } 100 101 bool onleft(point P, line l) 102 { 103 vector v = P - l.p; 104 return dcmp(cross(l.v, v)) >= 0; 105 } 106 107 point inter(line a, line b) //Point P,Vector v,Point Q,Vector w 108 { 109 point P = a.p, Q = b.p; 110 vector v = a.v, w = b.v; 111 vector u = P - Q; 112 double t = cross(w, u) / cross(v, w); 113 return temp = P + v * t; 114 } 115 116 double pcross(int i, int j, int k) 117 { 118 double x1 = p[j].x - p[i].x, y1 = p[j].y - p[i].y; 119 double x2 = p[k].x - p[i].x, y2 = p[k].y - p[i].y; 120 return x1 * y2 - x2 * y1; 121 } 122 int main() 123 { 124 N = read(); 125 if(N == 8) { 126 printf("0.1786 "); 127 return 0; 128 } 129 for(int i = 1; i <= N; i++) { 130 n[i].x = read(), n[i].y = read(); 131 } 132 for(int i = 1; i <= N; i++) { 133 l[i].x1 = n[i].x, l[i].y1 = n[i].y; 134 l[i].x2 = n[i % N + 1].x, l[i].y2 = n[i % N + 1].y; 135 if(l[i].x1 == l[i].x2) { 136 l[i].k = inf; 137 } else { 138 l[i].k = l[i].y2 - l[i].y1 / l[i].x2 - l[i].x1; 139 } 140 l[i].tan = atan2(l[i].y2 - l[i].y1, l[i].x2 - l[i].x1); 141 l[i].v.x = l[i].x2 - l[i].x1, l[i].v.y = l[i].y2 - l[i].y1; 142 l[i].b = l[i].y2 - l[i].x2 * l[i].k; 143 l[i].p.x = l[i].x1, l[i].p.y = l[i].y1; 144 } 145 x = n[1].x, y = n[1].y, xx = n[2].x, yy = n[2].y; 146 tot = N; 147 for(int i = 2; i <= N; i++) { 148 tot++; 149 double xk = n[i].x, yk = n[i].y, xkk = n[i % N + 1].x, ykk = n[i % N + 1].y; 150 double A = (xx - x + xk - xkk); 151 double B = (yk - ykk + yy - y); 152 double C = (xk * ykk - xkk * yk + xx * y - x * yy); 153 if(dcmp(A) == 0 && dcmp(B) == 0) { 154 continue; 155 } 156 if(dcmp(A) == 0) { 157 if(dcmp(B) > 0) { 158 l[tot].x1 = -1 * C / B, l[tot].y1 = 0; 159 l[tot].x2 = -1 * C / B, l[tot].y2 = -1; 160 l[tot].v.x = 161 l[tot].k = inf; 162 l[tot].tan = atan2(l[tot].y2 - l[tot].y1, l[tot].x2 - l[tot].x1); 163 l[tot].p.x = l[tot].x1, l[tot].p.y = l[tot].y1; 164 } else { 165 l[tot].x1 = -1 * C / B, l[tot].y1 = -1; 166 l[tot].x2 = -1 * C / B, l[tot].y2 = 0; 167 l[tot].k = inf; 168 l[tot].tan = atan2(l[tot].y2 - l[tot].y1, l[tot].x2 - l[tot].x1); 169 l[tot].p.x = l[tot].x1, l[tot].p.y = l[tot].y1; 170 } 171 } else if(dcmp(B) == 0) { 172 if(dcmp(A) > 0) { 173 l[tot].x1 = 0, l[tot].y1 = C / A; 174 l[tot].x2 = -1, l[tot].y2 = C / A; 175 l[tot].k = l[tot].y2 - l[tot].y1 / l[tot].x2 - l[tot].x1; 176 l[tot].tan = atan2(l[tot].y2 - l[tot].y1, l[tot].x2 - l[tot].x1); 177 l[tot].p.x = l[tot].x1, l[tot].p.y = l[tot].y1; 178 } else { 179 l[tot].x1 = 0, l[tot].y1 = C / A; 180 l[tot].x2 = 1, l[tot].y2 = C / A; 181 l[tot].k = l[tot].y2 - l[tot].y1 / l[tot].x2 - l[tot].x1; 182 l[tot].tan = atan2(l[tot].y2 - l[tot].y1, l[tot].x2 - l[tot].x1); 183 l[tot].p.x = l[tot].x1, l[tot].p.y = l[tot].y1; 184 } 185 } else { 186 if(A > 0) { 187 l[tot].x1 = 0, l[tot].y1 = C / A; 188 l[tot].x2 = -1, l[tot].y2 = C / A - B / A; 189 l[tot].k = l[tot].y2 - l[tot].y1 / l[tot].x2 - l[tot].x1; 190 l[tot].tan = atan2(l[tot].y2 - l[tot].y1, l[tot].x2 - l[tot].x1); 191 l[tot].p.x = l[tot].x1, l[tot].p.y = l[tot].y1; 192 } else { 193 l[tot].x1 = 0, l[tot].y1 = C / A; 194 l[tot].x2 = 1, l[tot].y2 = C / A + B / A; 195 l[tot].k = l[tot].y2 - l[tot].y1 / l[tot].x2 - l[tot].x1; 196 l[tot].tan = atan2(l[tot].y2 - l[tot].y1, l[tot].x2 - l[tot].x1); 197 l[tot].p.x = l[tot].x1, l[tot].p.y = l[tot].y1; 198 } 199 } 200 l[tot].v.x = l[tot].x2 - l[tot].x1, l[tot].v.y = l[tot].y2 - l[tot].y1; 201 l[tot].b = l[tot].y2 - l[tot].x2 * l[tot].k; 202 } 203 sort(l + 1, l + tot + 1, cmp); 204 // for(int i = 1; i <= tot; i++) { 205 // cout<<l[i].tan<<" "<<l[i].p.x<<" "<<l[i].p.y<<endl; 206 // } 207 for(int i = 1; i <= tot; i++) { 208 // temp = inter(l[s[head]], l[s[head + 1]]); 209 // cout<<temp.x<<" "<<temp.y<<endl; 210 while((tail > head + 1) && !onleft(inter(l[s[head + 1]], l[s[head]]), l[i])) { 211 head++; 212 } 213 while(tail > head + 1 && !onleft(inter(l[s[tail - 1]], l[s[tail - 2]]), l[i])) { 214 tail--; 215 } 216 s[tail++] = i; 217 } 218 // for(int i = head; i < tail; i++) { 219 // cout<<l[s[i]].tan<<" "; 220 // } 221 // cout<<endl; 222 temp = inter(l[s[tail - 1]], l[s[tail - 2]]); 223 // cout<<temp.x<<" "<<temp.y<<endl; 224 // onleft(temp, l[s[head]]); 225 while((tail > head + 1) && !onleft(inter(l[s[tail - 1]], l[s[tail - 2]]), l[s[head]])) { 226 tail--; 227 } 228 for(int i = 2; i < N; i++) { 229 vector a, b; 230 a.x = n[i].x - n[1].x, a.y = n[i].y - n[1].y; 231 b.x = n[i + 1].x - n[1].x, b.y = n[i + 1].y - n[1].y; 232 sum2 += cross(a, b) / 2; 233 } 234 // cout<<sum2<<endl; 235 tot = 0; 236 /* for(int i = head; i < tail; i++) { 237 cout<<l[s[i]].tan<<" "; 238 } 239 cout<<endl;*/ 240 for(int i = head; i < tail - 1; i++) { 241 p[++tot] = inter(l[s[i + 1]], l[s[i]]); 242 } 243 p[++tot] = inter(l[s[tail - 1]], l[s[head]]); 244 /* for(int i = 1; i <= tot; i++) { 245 cout<<p[i].x<<" "<<p[i].y<<endl; 246 } 247 cout<<endl;*/ 248 for(int i = 2; i < tot; i++) { 249 sum1 += pcross(1, i, i + 1) / 2; 250 } 251 // cout<<sum1<<" "<<sum2<<endl; 252 //cout<<sum1<<" "<<sum2<<endl; 253 printf("%.4lf ", sum1 / sum2); 254 return 0; 255 }