codeforces 814D An overnight dance in discotheque（几何思维）

84 阅读 0 评论 56 点赞

我是靠谱客的博主唠叨小鸭子，最近开发中收集的这篇文章主要介绍codeforces 814D An overnight dance in discotheque（几何思维），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

D. An overnight dance in discotheque
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
The crowdedness of the discotheque would never stop our friends from having fun, but a bit more spaciousness won’t hurt, will it?

The discotheque can be seen as an infinite xy-plane, in which there are a total of n dancers. Once someone starts moving around, they will move only inside their own movement range, which is a circular area Ci described by a center (xi, yi) and a radius ri. No two ranges’ borders have more than one common point, that is for every pair (i, j) (1 ≤ i < j ≤ n) either ranges Ci and Cj are disjoint, or one of them is a subset of the other. Note that it’s possible that two ranges’ borders share a single common point, but no two dancers have exactly the same ranges.

Tsukihi, being one of them, defines the spaciousness to be the area covered by an odd number of movement ranges of dancers who are moving. An example is shown below, with shaded regions representing the spaciousness if everyone moves at the same time.

But no one keeps moving for the whole night after all, so the whole night’s time is divided into two halves — before midnight and after midnight. Every dancer moves around in one half, while sitting down with friends in the other. The spaciousness of two halves are calculated separately and their sum should, of course, be as large as possible. The following figure shows an optimal solution to the example above.

By different plans of who dances in the first half and who does in the other, different sums of spaciousness over two halves are achieved. You are to find the largest achievable value of this sum.

Input
The first line of input contains a positive integer n (1 ≤ n ≤ 1 000) — the number of dancers.

The following n lines each describes a dancer: the i-th line among them contains three space-separated integers xi, yi and ri ( - 106 ≤ xi, yi ≤ 106, 1 ≤ ri ≤ 106), describing a circular movement range centered at (xi, yi) with radius ri.

Output
Output one decimal number — the largest achievable sum of spaciousness over two halves of the night.

The output is considered correct if it has a relative or absolute error of at most 10 - 9. Formally, let your answer be a, and the jury’s answer be b. Your answer is considered correct if .

Examples
input
5
2 1 6
0 4 1
2 -1 3
1 -2 1
4 -1 1
output
138.23007676
input
8
0 0 1
0 0 2
0 0 3
0 0 4
0 0 5
0 0 6
0 0 7
0 0 8
output
289.02652413
Note
The first sample corresponds to the illustrations in the legend.

题意：有很多人跳舞，跳舞范围是个圆，然后跳舞的人分上半夜和下半夜，同一个圈圈里面的人不能同时跳。让你把所有能跳圈圈的面积加起来，得到的面积最大。

贪心就好。把所有圈圈被覆盖的次数统计一下，最大那个肯定加，然后奇数大的加进去，偶数大的减掉，最大的可以在上半夜跳，然后奇数大的在下半夜跳，这就是第一个样例，吗的
破英语
No two ranges’ borders have more than one common point,
这句话告诉我们，没有多于一个的公共点，那就是相嵌了

判断两圆相交条件，圆心距小于两圆半径之和
所以 ans=s(1)+s(2)-s(3)+s(4)-s(5)+…

#include <bits/stdc++.h>
using namespace std;
const double pi=acos(-1.0);
struct node
{
double x,y,r;
double area()
{
return pi*r*r;
}
}s[1010];
int vis[1010];
int cmp(node a,node b)
{
if(a.r==b.r)
{
if(a.x==b.x) return a.y<b.y;
return a.x<b.x;
}
return a.r>b.r;
}
int han(node a,node b)
{
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)<(a.r+b.r)*(a.r+b.r);
}
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%lf%lf%lf",&s[i].x,&s[i].y,&s[i].r);
}
sort(s+1,s+n+1,cmp);
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
if(han(s[i],s[j])) vis[j]++;
}
}
double sum=0;
for(int i=1;i<=n;i++)
{
if(!vis[i]) sum+=s[i].area();
else if(vis[i]&1)
{
sum+=s[i].area();
}
else sum-=s[i].area();
}
printf("%.7fn",sum);
}