2015年4月6日 星期一

2015/04/06 USACO 2013 November Contest, Gold Problem 2. Line of Sight

// http://www.usaco.org/index.php?page=viewproblem2&cpid=347
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <queue>
#include <cmath>

using namespace std;

double PI = acos(-1);

int N, R;

typedef pair<double, double> pr;
#define a first
#define b second

pr pt[150000];

int main()
{
    freopen("sight.in", "r", stdin);
    freopen("sight.out", "w", stdout);

    scanf("%d %d", &N, &R);

    for(int Ni = 0; Ni < N; Ni++)
    {
        double x, y;
        scanf("%lf %lf", &x, &y);

        double bs = atan2(y, x);

        double d = sqrt(x*x+y*y);
        double c = acos(R/d);

        if( bs-c <= 0 ) bs += PI*2;
        pt[Ni] = pr(bs-c, bs+c);
    }

    sort(pt, pt+N);

    for(int Ni = N; Ni < N*2-1; Ni++)
        pt[Ni] = pr(pt[Ni-N].a+PI*2, pt[Ni-N].b+PI*2);

    long long Ans = 0;

    for(int Ni = 0; Ni < N; Ni++)
    {
        int l = Ni, r = N*2-1;

        while( l+1 != r )
        {
            int mid = (l+r)/2;
            if( pt[mid].a <= pt[Ni].b ) l = mid;
            else r = mid;
        }

        Ans += l-Ni;
    }

    printf("%lld\n", Ans);
}

沒有留言:

張貼留言