coderforces 814 D. An overnight dance in discotheque（贪心）

题意：

一个坐标系上有若干个不相交的圆，可以将其中的一下圆放到第二个坐标系中去，问两个坐标系中被覆盖奇数次的区域的面积的最大值。

解题思路：

首先没有被包含的圆的面积是最大的，是一定要取的，直接放到第二个坐标系就好了，然后就可以直接两个坐标系分别求面积就好了，因为你会发现第一个坐标系的圆再往第二个移的话总面积也是不会变或者变小。主要的原因大概是第一个坐标系剩余的圆如果是嵌套的话，移动也没什么区别了，如果没有嵌套（包含）圆的话，只会使面积变小。

至于计算面积，其实不难，我们先n^2算一下每个圆被几个圆包含，然后对于被包含偶数次的圆，答案直接加上它的面积就行了，对于被包含奇数次的圆，答案减去它的面积。

代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn=1005;
struct p
{
double x, y;
double r;
double s;
}t[maxn], A[maxn];
int a[maxn][maxn];
int in[maxn];
int book[maxn];//is move
double dis(p a, p b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
bool judge(int x, int y)
{
return t[x].r>dis(t[x],t[y]);
}
int main()
{
int n, i, j;
cin>>n;
for(i=1; i<=n; i++)
{
scanf("%lf%lf%lf", &t[i].x, &t[i].y, &t[i].r);
t[i].s=acos(-1)*t[i].r*t[i].r;
}
for(i=1; i<=n; i++)
{
for(j=i+1; j<=n; j++)
{
if(t[i].r<t[j].r)
{
if(judge(j, i))
{
a[j][i]=1;
in[i]++;
}
}
else
{
if(judge(i, j))
{
a[i][j]=1;
in[j]++;
}
}
}
}
/*
for(i=1; i<=n; i++)
{
for(j=1; j<=n; j++)
{
if(a[i][j])
{
printf("%d %dn", i, j);
}
}
}
*/
int k=0;
double ans=0.0;
for(i=1; i<=n; i++)
{
if(in[i]==0)
{
for(j=1; j<=n; j++)
{
a[i][j]=a[j][i]=0;
}
ans+=t[i].s;
}
}
for(i=1; i<=n; i++)
{
if(in[i]!=0)
{
int num=0;
for(j=1; j<=n; j++)
{
num+=a[j][i];
}
if(num&1)
{
ans-=t[i].s;
//
printf(" -%dn", i);
}
else
{
ans+=t[i].s;
//
printf(" +%dn", i);
}
}
}
printf("%.9fn", ans);
}

最后

以上就是欣喜百褶裙为你收集整理的coderforces 814 D. An overnight dance in discotheque（贪心）的全部内容，希望文章能够帮你解决coderforces 814 D. An overnight dance in discotheque（贪心）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。