codeforces 814D An overnight dance in discotheque

正解：贪心。

首先我们可以计算出每个圆被多少个圆覆盖。

很显然，最外面的圆是肯定要加上的。

然后第二层的圆也是要加上的。那么第三层就不可能被加上了。同理，第四层的圆又一定会被加上。

然后我们可以发现一个贪心策略，没被覆盖和被覆盖奇数次的圆加上，被覆盖偶数次的圆减去。

可以发现这样的贪心策略是最优的。

 #include <bits/stdc++.h>

 #define il inline

 #define RG register

 #define ll long long

 #define N (1005)

 using namespace std;

 const double pi=acos(-1.0);

 double x[N],y[N],r[N],ans;

 int cov[N],n;

 il int gi(){

   RG int x=,q=; RG char ch=getchar();

   while ((ch<'' || ch>'') && ch!='-') ch=getchar();

   if (ch=='-') q=-,ch=getchar();

   while (ch>='' && ch<='') x=x*+ch-,ch=getchar();

   return q*x;

 }

 il double dis(RG int i,RG int j){

   return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));

 }

 il int check(RG int i,RG int j){

   return r[i]<r[j] && dis(i,j)<=r[j]-r[i];

 }

 int main(){

 #ifndef ONLINE_JUDGE

   freopen("dance.in","r",stdin);

   freopen("dance.out","w",stdout);

 #endif

   n=gi();

   for (RG int i=;i<=n;++i) x[i]=gi(),y[i]=gi(),r[i]=gi();

   for (RG int i=;i<=n;++i)

     for (RG int j=;j<=n;++j){

       if (i==j) continue; cov[i]+=check(i,j);

     }

   for (RG int i=;i<=n;++i)

     if (!cov[i]) ans+=pi*r[i]*r[i];

     else if (cov[i]&) ans+=pi*r[i]*r[i];

     else ans-=pi*r[i]*r[i];

   printf("%0.8lf\n",ans); return ;

 }

巴特西

codeforces 814D An overnight dance in discotheque

最新文章

热门文章