Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 1725 Solved: 743
[Submit][Status][Discuss]
Description
有n个圆盘从天而降，后面落下的可以盖住前面的。求最后形成的封闭区域的周长。看下面这副图, 所有的红
色线条的总长度即为所求.
Input
第一行为1个整数n,N<=1000
接下来n行每行3个实数,ri,xi,yi,表示下落时第i个圆盘的半径和圆心坐标.
Output
最后的周长，保留三位小数
Sample Input
2
1 0 0
1 1 0
1 0 0
1 1 0
Sample Output
10.472
这题让我想到了线段覆盖。。。输错一个double调了我一晚上
利用三角函数求出每个圆盘覆盖先前圆盘弧度的范围，最后统计总共覆盖了多少弧度，计算出没有被覆盖的弧度大小，乘以半径就是周长
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iterator>
#include<vector>
using namespace std; const int MAXN=;
const double pi=acos(-1.0);
#define sqr(x) (x)*(x) struct Line
{
double l,r;
};
double r[MAXN],x[MAXN],y[MAXN];
vector<Line> L[MAXN];
vector<Line>::iterator iter; int n;
double ans; bool cmp(Line a,Line b)
{
return a.l<b.l;
} double dist(int a,int b)
{
return sqrt(sqr(x[a]-x[b])+sqr(y[a]-y[b]));
} bool conta(int a,int b)
{
return r[a]-r[b]>=dist(a,b);
} bool inter(int a,int b)
{
return r[a]+r[b]>=dist(a,b);
} void insrad(int a,int b)
{
double d=dist(a,b);
double rad=acos((sqr(r[a])+sqr(d)-sqr(r[b]))/(*r[a]*d));
double st=atan2(x[a]-x[b],y[a]-y[b]);
if(st-rad<-pi)
{
L[a].push_back((Line){st-rad+*pi,pi});
L[a].push_back((Line){-pi,st+rad});
return;
}
if(st+rad>pi)
{
L[a].push_back((Line){st-rad,pi});
L[a].push_back((Line){-pi,st+rad-*pi});
return;
}
L[a].push_back((Line){st-rad,st+rad});
} double cal(int x)
{
for(int i=x+;i<=n;i++)
if(conta(i,x)) return ;
for(int i=x+;i<=n;i++)
if(!conta(x,i)&&inter(x,i))
insrad(x,i);
sort(L[x].begin(),L[x].end(),cmp);
double t=,last=-pi;
for(iter=L[x].begin();iter!=L[x].end();iter++)
if(iter->l>last)
{
t+=iter->l-last;
last=iter->r;
}
else last=max(last,iter->r);
t+=pi-last;
return t*r[x];
} int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%lf %lf %lf",&r[i],&x[i],&y[i]);
for(int i=;i<=n;i++)
ans+=cal(i);
printf("%.3lf\n",ans);
return ;
}