Sky Garden

題意：

畫n個圓和m條直線，圓的中心點為(0,0)，圓的半徑分別從1到n，而直線都必經過(0,0)點，并且所有直線會把每個圓平均分成2m個面積相等的區(qū)域，直線會和圓形成交點，求所有交點兩兩經過線的最短路徑的和。

題解：

因為題目多圓，多線，所以我們分類討論
情況一：對于一個圓上的兩個點，他們之間的最短距離是圓弧的長度或者是兩者到圓心的距離和，即圖中的粉色和綠色部分

情況二：對于不是一個圓上的兩個點A和B，他們之間的最短距離是從外圈圓B通過直線到內圈圓C，然后C到A的最短距離
如圖

具體步驟：
1… 我們首先要計算中心交點到個點的距離和，對于半徑為i的圓上交點A，A到圓心的距離為A，一共n個圓，距離就是1+…+n = n * (1+n)/2,然后有m條直線，也就是2 * m個從原點延伸的方向，每個方向都是這種情況，所以答案就是 n * (1+n) * m
2. 我們要按照從內圓到外圓的方式來計算，每此執(zhí)行都用sum來記錄圓內某點到其他點（其他共2 * m -1個）的距離和。圖一A到B的圓心距離和為i+i，（i為第i個圓，半徑也就是i），圓弧距離為 2 * pi * i * (j/2m), 2 * pi * i 好理解就是圓的周長，后面這個(j/2m)是什么意思？因為圓被分為2m份，有2 * m個射線，j表示一側的第j+1個邊，我們考慮第一個線和第j+1個線之間的圓弧情況。然后（pi * i * j）和2 * i比較大小選擇即可
圖中的三個綠色弧線，分別表示j=1,2，3
我們求完一側后，根據(jù)對稱性另一側也就知道了，所以前兩個弧*2再加上最后一段弧（因為左側只需要考慮兩個點）
對于第一個射線是這么考慮，一共2 * m個射線 ，sum要乘2m

，但是這樣是存在重復的，我們考慮第一條射線（綠色）和第二條射線（紫色），發(fā)現(xiàn)藍色畫圈部分是重復計算的，同理其他射線也是如此。相當于綠色部分的邊（除了最長的那個半圓邊）都重復了2 * m次，最長的那個半圓邊重復了m次，所以記得減去

完成圓內計算后，就需要計算圓內各點到外層圓上各點的最短距離和，我們根據(jù)情況二得到圓內某個點到達外層圓上的所有點的距離和為m * (1+(n-i)) * (n-i)+sum * (n-i)，
m * (1+(n-i)) * (n-i)是當前第i層圓上某點到達外層圓上各點時走到直線上的路程，圖二中C到B的過程
式子是怎么得到的：
從C到B再往外，距離是1+…+n-i
求和然后乘2m就是m * (1+(n-i)) * (n-i)
sum * (n-i)則計算的是圓內某點到達外層圓上各點投影到當前圓上各點的距離和，也就是圖二中A到C的過程
最后要乘2m
這個題說簡單簡單，說難也難。。。
好好考慮考慮

代碼：

#include<bits/stdc++.h> using namespace std; const double pi = acos(-1);int main() {int n,m;scanf("%d %d",&n,&m);double ans=0;if(m!=1) ans=ans+(1+n)*n*m;for(int i=1;i<=n;i++){double sub=0;double sum=0;for(int j=1;j<=m;j++){if(j==m){sub=sub+m*2*i;sum=sum*2+2*i;}else{if((pi*i*j)/m<2*i){sum=sum+(pi*i*j)/m;sub=sub+2*m*((pi*i*j)/m);}else{sum=sum+2*i;sub=sub+2*m*2*i;}}}ans+=sum*2*m-sub;ans=ans+(m*(1+(n-i))*(n-i)+sum*(n-i))*2*m;}printf("%.10f\n",ans);return 0; }

總結

以上是生活随笔為你收集整理的Sky Garden的全部內容，希望文章能夠幫你解決所遇到的問題。

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