1043: [HAOI2008]下落的圆盘
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 887 Solved: 359
[Submit][Status][Discuss]
Description
有n个圆盘从天而降,后面落下的可以盖住前面的。求最后形成的封闭区域的周长。看下面这副图, 所有的红色线条的总长度即为所求.
Input
n ri xi y1 … rn xn yn
Output
最后的周长,保留三位小数
Sample Input
2
1 0 0
1 1 0
Sample Output
10.472
HINT
数据规模
n<=1000
Source
暴力枚举每个圆后面的所有圆
对这些圆每个与当前圆计算覆盖的弧度(有两个半径一个圆心距可以用余弦定理)
把算出来的这些弧度存进栈里
最后一起统计一下总共覆盖多少弧度,再计算剩余部分弧长
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define MAXN 1010
#define eps 1e-9
#define MAXDBL 1e20
#define pi acos(-1)
using namespace std;
int n,top;
double ans,sum,temp;
struct Bug
{
double lb,rb;
bool operator <(const Bug& a)const
{
return lb!=a.lb?lb<a.lb:rb<a.rb;
}
}sta[MAXN];
struct circle
{
double x,y,r;
}s[MAXN];
inline double sqr(double x)
{
return x*x;
}
inline double dis(circle a,circle b)
{
return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));
}
inline bool in(circle a,circle b)
{
return a.r>=b.r+dis(a,b);
}
inline void circle_cross_circle(circle a,circle b)
{
double Dis=dis(a,b),tmp,st,bugle;
tmp=(sqr(a.r)-sqr(b.r)+sqr(Dis))/(Dis*2);
st=atan2((a.x-b.x),(a.y-b.y));
bugle=acos(tmp/a.r);
sta[++top]=(Bug){(st-bugle),(st+bugle)};
}
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++) scanf("%lf%lf%lf",&s[i].r,&s[i].x,&s[i].y);
for (int i=1;i<=n;i++)
{
top=0;sum=0;temp=0;
bool flag=0;
for (int j=i+1;j<=n;j++)
if (in(s[j],s[i]))
{
flag=1;
break;
}
if (flag) continue;
for (int j=i+1;j<=n;j++)
if (!in(s[i],s[j])&&s[i].r+s[j].r>=dis(s[i],s[j])) circle_cross_circle(s[i],s[j]);
for (int j=1;j<=top;j++)
{
while (sta[j].lb<0) sta[j].lb+=2*pi;
while (sta[j].rb<0) sta[j].rb+=2*pi;
if (sta[j].lb>sta[j].rb) sta[++top]=(Bug){0,sta[j].rb},sta[j].rb=2*pi;
}
sort(sta+1,sta+top+1);
for (int j=1;j<=top;j++)
if (sta[j].lb>temp) sum+=sta[j].lb-temp,temp=sta[j].rb;
else temp=max(temp,sta[j].rb);
sum+=2*pi-temp;
ans+=s[i].r*sum;
}
printf("%.3f\n",ans);
}