Codeforces 681E Runaway to a Shadow【计算几何】

题目链接:

http://codeforces.com/problemset/problem/681/E

题意:

给定小强初始位置,以及若干圆的圆心和半径。已知小强以均等概率选择前进方向,给定速度和时间,做匀速直线运动。问小强在给定时间内走进圆的概率。

分析:

建立坐标系,以小强初始位置为原点,只要求出以原点为圆心,半径为$T \times V$的圆$O$与其他每个圆相交的部分构成的弧度,再取个并集,那么概率即为$并集大小\over 2\pi$。
如何求弧度并集?利用余弦定理求出相交部分的弧度,注意弧度存在范围,当原点与交点的连线$L$与圆相切的时候,弧度到达最大,那么在计算的时候只要将$L$跟切线长取个最小值即可~再利用小圆的圆心与$x$轴正方向的弧度,就可以求出两个边界的弧度了。最后就是所有弧度取个并集就好了~
【沙茶如我以为这样就结束了。
注意!弧度范围为$[0,2\pi]$,要对于$a-b \lt 0 和 a+b \gt 2\pi$的情况进行一下处理!orz

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<cmath>
#include<algorithm>
using namespace std;
typedef pair<double, double> pd;
const int maxn = 1e5 + 5;
double pi = acos(-1.0), eps = 1e-8;
struct POINT{
double x, y, r;
double dist(){
return x * x + y * y;
}
double angel(){
double a = atan2(y, x);
if(a < -eps) a += 2 * pi;
return a;
}
}p[maxn];
int main (void)
{
double x0, y0, V, T;
int n;
scanf("%lf%lf%lf%lf%d", &x0, &y0, &V, &T, &n);
double x, y, r;
double mx = T * V;
for(int i = 0; i < n; i++){
scanf("%lf%lf%lf", &x, &y, &r);
x -= x0; y -=y0;
p[i] = (POINT){x, y, r};
}
vector<pd>v;
for(int i = 0; i < n; i++){
if(p[i].dist() - p[i].r * p[i].r < eps) return printf("1.000000000\n"), 0;
if(sqrt(p[i].dist()) - eps > p[i].r + mx) continue;
double d1 = min(sqrt(p[i].dist() - p[i].r * p[i].r), mx);
double b = acos((p[i].dist() + d1 * d1 - p[i].r * p[i].r) / (2.0 * sqrt(p[i].dist()) * d1));
double a = p[i].angel();
if(a + b - eps > 2 * pi){
v.push_back(pd(a - b, 2 * pi));
v.push_back(pd(0, a + b - 2 * pi));
}else if(a - b < -eps){
v.push_back(pd(0, a + b));
v.push_back(pd(a - b + 2 * pi, 2 * pi));
}else{
v.push_back(pd(a - b, a + b));
}
}
if(!v.size()) return printf("0.000000000\n"), 0;
sort(v.begin(), v.end());
double ans = 0.0;
double l = v[0].first;
r = v[0].second;
int sz = v.size();
for(int i = 1; i < sz; i++){
if(v[i].first + eps > r){
ans += r - l;
l = v[i].first;
}
if(v[i].second + eps > r){
r = v[i].second;
}
}
ans += r - l;
printf("%.10f\n", ans / (2.0 * pi));
return 0;
}
文章目录
  1. 1. 题目链接:
  2. 2. 题意:
  3. 3. 分析:
  4. 4. 代码: