P8031 题解

· · 题解

题目分析

从反面考虑。

对于每个点 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;
}