Codeforces Round #357 (Div. 2) E. Runaway to a Shadow

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

바퀴벌레의 좌표와 속도, 시간이 주어지고

N개의 접시에 대한 정보(좌표와 반지름)가 주어질 때

바퀴벌레가 접시 안에 들어가면 살 수 있는데 처음에 정한 방향으로만 갈 수가 있을 때, 바퀴벌레가 살 수 있는 확률을 구하는 문제

우선 바퀴벌레의 속도와 시간을 곱하면 바퀴벌레가 갈 수 있는 최대 거리가 되며, 바퀴벌레의 위치를 중심으로하고 반지름이

최대 거리인 원을 그렸을 때 접시들과 겹치는 방향들의 seq 들의 합집합의 각도들의 합에 대해 2π 로 나눠 주면 답이 된다.

일단 하나의 접시에 대해서만 생각해 보자. 

우선 바퀴벌레의 이동가능 범위 원과 접시가 겹치지 않는다면 이 접시는 살 수 있는 확률을 전혀 증가시켜 주지 않는다.

그렇다면 겹치는 경우에는 어떨까? 두가지 케이스가 있다. 

1. 바퀴벌레의 위치에서 접시에 접선을 하나 그었을 때 접점이 바퀴벌레의 이동가능 범위 원 내에 있는경우

2. 밖에 있는 경우

1 번의 경우에는 두 접선의 사이로 가기만하면 살 수가 있기 때문에 두 원의 중심을 이은 선과 접선이 이루는 각 theta는 

간단하게 사인값을 통해 구할 수가 있다.(asin 사용)

2 번의 경우에는 두 원의 두 교점사이에 가야 살 수가 있기 때문에 이 것은 제 2 코사인 법칙으로 구한다. 삼각형의 세 변의 길이를

알 수가 있기 때문에 cos 값을 구할 수가 있으므로 acos 를 사용한다.

방향을 x축의 양의 방향을 기준으로 잰 각도로 나타내보면 살 수 있게 되는 방향들은 left 각도와 right 각도 이렇게 두 각도로

sequence 로서 표현할 수가 있다. 

그렇다면 두개의 접시를 보자. 두 접시 각각의 sequence 가 겹친다면 따로따로 계산해서 더하면 제대로된 답이 나오질 않을 것이다.

 그렇다면 이것을 어떻게 할까?

겹치는 N개의 구간들을 봐주는 것에 있어서 스위핑이 금방 떠오를 것이다.. 

하지만 여기서 고려해 주어야 하는 것이 두개 있다..

그냥 수직선 상에서 스위핑을 할 때는 신경 써주지 않아도 되는것인데

원에서 360도에 대해 스위핑을 하다보니 문제가 생기는것이다.

맨 처음 시작하는 기준이 되는 각도 start가 있다고 쳤을 때

seq의 left 와 right 가 start 를 사이에 두고 걸쳐 있다면 문제가 될 수가 있다..

또 두번째는 2π 를 더하고 빼면 결국 같은 각도이기 때문에 정렬을 할 때 연속되게 하여 제대로 계산하려면

left 와 right 가 특정 범위내에 있도록 맞춰주기 위해 변환해 주어야한다.

예를들어 -7/6 π 와 5/6 π 와 결국 같은 위치인데 하나로 맞춰 주지 않으면 정렬했을 때 붙어있지 않고

사이에 다른 많은 seq들이 존재 하게 되어 제대로된 계산이 되지도 않고 중복해서 계산하게 될 것이다.

아무튼 이 두가지를 잘 신경 써주어 스위핑을 하면 된다.

#include <bits/stdc++.h>
#define REP(i,a,b) for(int i=a;i<=b;++i)
#define FOR(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define sz(v) ((int)(v).size())
#define inp1(a) scanf("%d",&a)
#define inp2(a,b) scanf("%d%d",&a,&b)
#define inp3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define inp4(a,b,c,d) scanf("%d%d%d%d",&a,&b,&c,&d)
#define inp5(a,b,c,d,e) scanf("%d%d%d%d%d",&a,&b,&c,&d,&e)
#define fastio() ios_base::sync_with_stdio(false),cin.tie(NULL)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<int> vi;    
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<vector<int> > vvi;
typedef pair<int,pair<int,int> > piii;
typedef vector<piii> viii;
const double EPSILON = 1e-9;
const double PI = acos(-1);
const int MOD = 1e9+7;
const int INF = 0x3c3c3c3c;
const long long INFL = 0x3c3c3c3c3c3c3c3c;
const int MAX_N = 102;
 
struct vector2{
    double x,y;
    vector2(){}
    vector2(double x, double y): x(x), y(y){}
    double hypot(){
        return sqrt(x*x+y*y);
    }
    double hypotPow(){
        return x*x+y*y;
    }
    double pos(){
        return atan2(y,x);
    }
};
struct circle{
    vector2 pos;
    double r;
    circle(){}
    circle(double x, double y, double r){
        pos.x = x;
        pos.y = y;
        r = r;
    }
};
 
double X, Y, V, T, R;
int N;
circle circles[100003];
vector<pair<double, double> > seqs;
double sqr(double x){return x*x;}
double findTheta(double a, double b, double c){
    return acos((a*a+b*b-c*c)/(2*a*b));
}
double myCos(double a, double b, double c){
    return (a*a+b*b-c*c)/(2*a*b);
}
int dcmp(double x){
    if(fabs(x) < EPSILON) return 0;
    return x < 0.0 ? -1 : 1;
}
 
int main() {
    scanf("%lf%lf%lf%lf",&X,&Y,&V,&T);
    R = V*T;
    scanf("%d",&N);
    bool found = false;
    for(int i = 0 ; i < N; i++) {
        scanf("%lf%lf%lf",&circles[i].pos.x, &circles[i].pos.y, &circles[i].r);
        if(found) continue;
        circles[i].pos.x -= X;
        circles[i].pos.y -= Y;
        if(dcmp(sqr(circles[i].pos.x)+sqr(circles[i].pos.y)-sqr(circles[i].r)) <= 0) {
            found = true;
            continue;
        }
    }
 
    X = Y = 0;
    if(found){
        printf("1.0000000");
        return 0;
    }
    if(dcmp(R) == 0){
        printf("0.0000000");
        return 0;
    }
 
    vector<pair<double, int> > a;
 
    for (int i = 0; i < N; i++) {
        double r = circles[i].r;
        double theta;
        double d = circles[i].pos.hypot();
        if(dcmp(circles[i].pos.hypot()-(R+r)) >= 0) continue;
        if(dcmp(d-R) <= 0) theta = asin(r/d);
        else theta = findTheta(d,R,r);
        double angM = circles[i].pos.pos();
        if(dcmp(angM)<=0) angM += 2*PI;
        double angL = angM - theta;
        double angR = angM + theta;
 
        if (dcmp(angL) < 0) {
            a.push_back(make_pair(angL + 2 * PI, 1));
            a.push_back(make_pair(2 * PI, -1));
            a.push_back(make_pair(0.0, 1));
            a.push_back(make_pair(angR, -1));
        } else if (dcmp(angR - 2*PI) > 0) {
            a.push_back(make_pair(angL, 1));
            a.push_back(make_pair(2 * PI, -1));
            a.push_back(make_pair(0.0, 1));
            a.push_back(make_pair(angR - 2 * PI, -1));
        } else {
            a.push_back(make_pair(angL, 1));
            a.push_back(make_pair(angR, -1));
        }
    }
 
    sort(a.begin(), a.end());
 
    double last = 0;
    int c = 0;
    double ans = 0;
 
    for (auto& p : a) {
        if (c > 0) {
            ans += p.first - last;
        }
        c += p.second;
        last = p.first;
    }
 
    ans /= 2 * PI;
    printf("%.11f", ans);
 
    return 0;
}