自动搬运

查看原文

来自洛谷，原作者为

	honglan0301 AFO —— 只是我的心一直在问，用什么把你永久留下～ | 2024.07.25 — ？

搬运于2025-08-24 22:35:18，当前版本为作者最后更新于2023-04-20 14:42:28，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目分析

从反面考虑。

对于每个点 $i$，先求出它到其它点的位置角 $α_i$，发现它不被覆盖等价于存在一个区间 $[α_0,α_0+\pi)$ 使得没有位置角位于该区间的点被选择（当然它自己也不能选）。于是我们枚举被选择的点中位置角最小的一个，然后双指针求出能够任意选择的点的个数即可（其它的必不能选），注意要断环成链地复制一遍数组。

时间复杂度 $O(n^2)$，可以通过本题。

代码

/*
  author: PEKKA_l  
  Sexy_goodier _ xiaoqing
 */
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define int long long
#define mod 1000000007
const double PI=acos(-1);

int n,x[1005],y[1005],ans;
double du[2005];

int ksm(int x,int k)
{
	int nx=x,na=1;
	for(int i=1;i<=k;i<<=1) {if(i&k) {na*=nx; na%=mod;} nx*=nx; nx%=mod;} return na;
}

signed main()
{
	cin>>n; for(int i=1;i<=n;i++) cin>>x[i]>>y[i]; ans=(n*ksm(2,n)%mod-n+mod)%mod;
	for(int i=1;i<=n;i++)
	{
		int cntt=0; for(int j=1;j<=n;j++) {if(j==i) continue; du[++cntt]=atan2(y[j]-y[i],x[j]-x[i]); du[cntt+n-1]=du[cntt]+2*PI;}
		sort(du+1,du+2*n-1); int nr=2; for(int nl=1;nl<=n-1;nl++) {while(du[nr]-du[nl]<PI) nr++; ans-=ksm(2,nr-nl-1); ans+=mod; ans%=mod;}
	}
	cout<<ans<<endl;
}