2016-09-08

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

代码：

#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;
}