[USACO13NOV] Line of Sight G 题解

· · 题解

前言

几何好题。

正文

题目大意应该很容易理解，就是问有多少点对不会被圆遮挡住。

在这里我们不失一般性的设出 A 和 B 点，做出下图：

容易发现，A 和 B 能互相看见，当且仅当他们在圆上的投影有相交的区域。

具体而言，我们分别从 A 点和 B 点往圆做切线，则他们在圆上的弧需要相交（即图中的 P'P 弧）。

那问题就转换成了在圆上重叠的弧的个数。

显然，弧和其圆内的角度有关，我们只需要考虑角度即可。

\angle AOP = \cos^{-1}(\frac{OP}{AO}) = \arccos (\frac{r}{\sqrt{x^2+y^2}}) \angle DOA = \tan^{-1}(\frac{HA}{OH}) = \arctan (\frac{y}{x})

显然，

\angle POD = \angle DOA - \angle AOP

则这个点在圆上投影弧的角度范围便是：

[\angle POD, \angle POD + 2 \times \angle AOP]

注意，有可能会出现负数，所以我们要加上 2\pi 补回正数。

后面就是线段重叠的板子，注意拆环的套路和答案统计的细节。

Code

#include <bits/stdc++.h>
#define int long long
#ifdef LOCAL
    #include "debug.h"
#else
    #define debug(...) 42
#endif
#define mkp make_pair
#define pb emplace_back
#define endl "\n"
using namespace std;
using ll = long long;
int n,r,t,cnt=0;
constexpr int maxn=1e5+10;
const double PI=acos(-1);

signed main(){
    cin.tie(nullptr)->sync_with_stdio(0);
    cin>>n>>r;
    vector<pair<double,double>> a;
    priority_queue<double,vector<double>,greater<double>> q;
    for(int i=0;i<n;i++){
        int x,y;cin>>x>>y;
        double alpha=acos(r/sqrt(1.0*x*x+y*y));
        double a0=atan2(y,x)-alpha;
        if(a0<0) a0+=2*PI;
        a.pb(mkp(a0,a0+2*alpha));
    }
    sort(a.begin(),a.end());
    for(int iters=0;iters<2;iters++){
        for(int i=0;i<n;i++){
            while(!q.empty()&&q.top()<a[i].first){
                q.pop();
            }
            if(iters==1) cnt+=q.size();
            q.push(a[i].second);
            a[i].first+=2*PI;
            a[i].second+=2*PI;
        }
    }
    cout<<cnt;
    return 0;
}