下落的圓盤

Time Limit: 10 Sec??Memory Limit: 162 MB
[Submit][Status][Discuss]

Description

　　有n個圓盤從天而降，后面落下的可以蓋住前面的。求最后形成的封閉區域的周長。

　　看下面這副圖, 所有的紅色線條的總長度即為所求。

　　

Input

　　第一行為1個整數n
　　接下來n行每行3個實數,ri,xi,yi,表示下落時第i個圓盤的半徑和圓心坐標.

Output

　　最后的周長，保留三位小數

Sample Input

　　2
　　1 0 0
　　1 1 0

Sample Output

　　10.472

HINT

　　n <= 1000

Solution

　　顯然是一道計算幾何題。

　　考慮一個圓對于答案的貢獻，顯然是這個圓的周長 - 后面的圓把它覆蓋掉的周長的并。那么我們就考慮怎么求這個并。

　　先考慮怎樣記錄下一個答案，顯然直接扣掉單個圓對它的覆蓋是不可行的，要減去重疊的情況。

　　既然邊不可行，我們就用角度。顯然，若我們求出 兩圓交點的角度 即可解決這題。

　　我們考慮求圓A被圓B覆蓋的角度：現在我們有兩個圓的半徑、圓心距。我們就可以得到 圓A與圓B的圓心連線 與 圓A半徑 的夾角。

　　我們也可以知道 圓A與圓B的圓心連線 與 x軸的夾角。

　　這樣的話，就可以把單個圓對于它的貢獻記錄到棧里面，最后掃一遍求一下剩余的角度，乘上R就是它對于答案的貢獻了。

Code

?

1 #include<iostream> 2 #include<string> 3 #include<algorithm> 4 #include<cstdio> 5 #include<cstring> 6 #include<cstdlib> 7 #include<cmath> 8 #include<queue> 9 using namespace std; 10 typedef unsigned long long s64; 11 12 const int ONE = 1000005; 13 const double pi = acos(-1.0); 14 15 int n; 16 struct power 17 { 18 double x, y, r; 19 }a[ONE]; 20 21 struct circle 22 { 23 double a, b; 24 }stk[ONE]; 25 int top; 26 27 double Ans; 28 29 bool cmp(const circle &a, const circle &b) 30 { 31 if(a.a != b.a) return a.a < b.a; 32 return a.b < b.b; 33 } 34 35 int get() 36 { 37 int res,Q=1; char c; 38 while( (c=getchar())<48 || c>57) 39 if(c=='-')Q=-1; 40 if(Q) res=c-48; 41 while((c=getchar())>=48 && c<=57) 42 res=res*10+c-48; 43 return res*Q; 44 } 45 46 double sqr(double x) {return x * x;} 47 double dist(power a, power b) {return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y));} 48 49 double Calc(power a, power b) 50 { 51 double A = a.r, B = b.r, C = dist(a, b); 52 double cosB = (sqr(A) + sqr(C) - sqr(B)) / (2 * A * C); 53 double angle = atan2(a.x - b.x, a.y - b.y), add = acos(cosB); 54 stk[++top] = (circle){angle - add, angle + add}; 55 } 56 57 double init(power a, power b) {return a.r + dist(a, b) <= b.r;} 58 double sect(power a, power b) {return fabs(a.r - b.r) < dist(a, b) && dist(a, b) < a.r + b.r;} 59 60 double Deal(int id) 61 { 62 top = 0; 63 for(int i = id+1; i <= n; i++) 64 if(init(a[id], a[i])) return 0; 65 66 for(int i = id+1; i <= n; i++) 67 if(sect(a[id], a[i])) Calc(a[id], a[i]); 68 69 for(int i = 1; i <= top; i++) 70 { 71 while(stk[i].a < 0) stk[i].a += 2 * pi; 72 while(stk[i].b < 0) stk[i].b += 2 * pi; 73 if(stk[i].a > stk[i].b) stk[++top] = (circle){0, stk[i].b}, stk[i].b = 2*pi; 74 } 75 76 sort(stk + 1, stk + top + 1, cmp); 77 double last = 0.0, sum = 0.0; 78 for(int i = 1; i <= top; i++) 79 if(stk[i].a > last) sum += stk[i].a - last, last = stk[i].b; 80 else last = max(last, stk[i].b); 81 82 sum += 2 * pi - last; 83 return a[id].r * sum; 84 } 85 86 int main() 87 { 88 n = get(); 89 for(int i = 1; i <= n; i++) 90 scanf("%lf %lf %lf", &a[i].r, &a[i].x, &a[i].y); 91 for(int i = 1; i <= n; i++) 92 Ans += Deal(i); 93 printf("%.3lf", Ans); 94 } View Code

?

轉載于:https://www.cnblogs.com/BearChild/p/7280763.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的【BZOJ1043】下落的圆盘 [计算几何]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。