「BZOJ1043」[HAOI2008] 下落的圆盘
Description
有n个圆盘从天而降，后面落下的可以盖住前面的。求最后形成的封闭区域的周长。看下面这副图, 所有的红色线条的总长度即为所求. 
Input
n ri xi y1 … rn xn yn
Output
最后的周长，保留三位小数
Sample Input
2
1 0 0
1 1 0
1 0 0
1 1 0
Sample Output
10.472
HINT
数据规模
n<=1000
题解
每个圆被其它每个圆盖住的部分是一段圆弧
求出这段圆弧
这图是不是很丑TAT。。。
根据r1^2-x^2=r2^2-(d-x)^2
得x=(r2^2-r1^2+d^2)/(2*d)
通过x和反三角函数就能算出弧的夹角，以及弧的左右端点角度，0<=l,r<=2*pi
对圆弧做贪心线段覆盖，得到每个圆对答案的贡献
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<set> #include<ctime> #include<queue> #include<cmath> #include<algorithm> #define ll long long #define pi acos(-1) using namespace std; int n,top; double ans; double x[1005],y[1005],r[1005]; struct line{double l,r;}q[1005]; bool operator<(line a,line b) { return a.l<b.l; } inline double dis(int a,int b) { return sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b])); } bool conta(int a,int b) { if(r[a]>=r[b]+dis(a,b))return 1; return 0; } void inter(int a,int b) { double d,t,st,l; d=dis(a,b); t=(r[a]*r[a]-r[b]*r[b]+d*d)/(2*d); st=atan2((x[a]-x[b]),(y[a]-y[b])); l=acos(t/r[a]); q[++top]=(line){(st-l),(st+l)}; } double cal(int x) { for(int i=x+1;i<=n;i++) if(conta(i,x))return 0; top=0; for(int i=x+1;i<=n;i++) { if(!conta(x,i)&&r[x]+r[i]>=dis(x,i))inter(x,i); } double tmp=0,now=0; for(int i=1;i<=top;i++) { if(q[i].l<0)q[i].l+=2*pi; if(q[i].r<0)q[i].r+=2*pi; if(q[i].l>q[i].r) { q[++top]=(line){0,q[i].r}; q[i].r=2*pi; } } sort(q+1,q+top+1); for(int i=1;i<=top;i++) if(q[i].l>now) { tmp+=q[i].l-now; now=q[i].r; } else now=max(now,q[i].r); tmp+=2*pi-now; return r[x]*tmp; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%lf%lf%lf",&r[i],&x[i],&y[i]); for(int i=1;i<=n;i++) ans+=cal(i); printf("%.3lf\n",ans); return 0; } |
计数器 9786139
OI 课件=>
OI 课件=>
QAQ学长图挂了
黄学长可以请问一下为什么35行atan2里面用的是(x,y)吗。。不管怎么看都应该是(y,x）但是总是不对TAT。。改成(x,y)就对了
atan2(对边，邻边） 我的代码中计算的是a->b圆心连线的倾角（竖直向下为0度）
两种效果一样的TT
根据r1^2-x^2=r1^2-(d-x)^2 应该改成
根据r1^2-x^2=r2^2-(d-x)^2