[USACO 2013 Gold] Line of Sight

作法：

如果兩個點可以互相看見，那麼就代表存在圓上的一個點，過他作出的切線會把那兩個點和 ( 0,0 ) 分在不同側。所以對於每個點 X ，假設他對圓作切線的兩個切點為 P , Q ，那麼把 PQ 這段弧記錄下來，然後看這 n 條弧裡面有幾對弧重合就是我們要的答案了。紀錄一段弧可以用起始和終止的角度來記錄，假設他們按照左端點排序之後變成了 p_1 ~ p_n ，而如果直接對得到的這些弧的角度區間算出「有幾對區間有重合」的話會漏掉一些東西，因為這是在圓上，所以反而有可能 p_n 和 p_1 有重合。解決方法是把 p_1 ~ p_n 全部都加上循環的週期 2*PI ，放在 p_(n+1) ~ p_(2n) 裡，對 p_1 ~ p_(2n) 求左區間是 p_1 ~ p_n 的答案即可。這樣會對主要是因為一個區間的長度 < 2*PI ，還有 p_1 ~ p_n 中任兩個區間的起始點差不會超過 2*PI ，所以不會重複算到或漏算。

code :

#include<bits/stdc++.h>
#define LL long long
#define DB double
#define pii pair<DB,DB>
#define F first
#define S second
using namespace std;
const int maxn=50000+10 ;
const DB PI=2*acos(0.0) ;
 
pii p[2*maxn] ;
main()
{
    freopen("sight.in","r",stdin) ;
    freopen("sight.out","w",stdout) ;
    int n ; DB r ; scanf("%d%lf",&n,&r) ;
    for(int i=1;i<=n;i++)
    {
        DB x,y ; scanf("%lf%lf",&x,&y) ;
        DB a=atan2(y,x) , b=acos(r/sqrt(x*x+y*y)) ;
        if(a-b<0) a+=2*PI ;
        p[i]=(pii){a-b,a+b} ;
    }
 
    sort(p+1,p+n+1) ;
    for(int i=1;i<=n;i++) p[i+n]=(pii){p[i].F+2*PI,p[i].S+2*PI} ;
    int ans=0 ;
    for(int i=1;i<=n;i++)
        ans+=lower_bound(p+1,p+2*n+1,(pii){p[i].S,p[i].S})-p-i-1 ;
 
    printf("%d\n",ans) ;
}