[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

CPP

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

[USACO13NOV] Line of Sight G 题解

文章操作

前言

正文

Code

相关推荐

评论

[USACO13NOV] Line of Sight G 题解