題意

把一個(gè)邊長(zhǎng)為1的正n邊形放到一個(gè)正m邊形中，要求m邊形完全覆蓋n邊形，可以有交點(diǎn)，并且中心重合。求正m邊形的最小邊長(zhǎng)，至少精確到6位。要求logn計(jì)算。

---

?

思考

先考慮m|n的情況。

我們知道，正m邊形的邊長(zhǎng)與可行區(qū)域（即可以完全覆蓋的那些角度）形成單射，當(dāng)且僅當(dāng)所有可行區(qū)域都成為可數(shù)的點(diǎn)時(shí)，答案最優(yōu)。（可以理解為再縮小一點(diǎn)就無(wú)解了）

這樣不難證明，把正n邊形的幾條邊剛好卡在正m邊形上是最優(yōu)的。如n=8，m=4：

這時(shí)正m邊形的邊長(zhǎng)是容易計(jì)算的。相信大家都會(huì)初中數(shù)學(xué)。

這樣再考慮一般情況。由于是中心重合，正n邊形旋轉(zhuǎn)2π/m度后仍然是能被覆蓋的。

在所有可行的旋轉(zhuǎn)過(guò)程中，將最外圈的點(diǎn)連起來(lái)，仍然形成一個(gè)正多邊形，且邊數(shù)為lcm(n,m)。

例如，n=4，m=6：

用紫線圍出來(lái)的正12邊形即為正方形得到的結(jié)果。

至于正確性，在于所有的可行區(qū)域都是單點(diǎn)。

這樣一來(lái)，就可以直接轉(zhuǎn)化為上一個(gè)問(wèn)題。公式認(rèn)真推即可。

---

?

代碼

1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long int ll; 4 const double pi=acos(-1); 5 ll n,m; 6 ll gcd(ll x,ll y) 7 { 8 return x%y==0?y:gcd(y,x%y); 9 } 10 ll lcm(ll x,ll y) 11 { 12 return x/gcd(x,y)*y; 13 } 14 double solve(ll n,ll m) 15 { 16 double len=1/(2*tan(pi/n)); 17 double th=(n/m)*pi/n; 18 return tan(th)*len*2; 19 } 20 int main() 21 { 22 ios::sync_with_stdio(false); 23 cin>>n>>m; 24 double len=1/(2*sin(pi/n)); 25 n=lcm(n,m); 26 double a=sin(pi/n)*len*2; 27 cout<<fixed<<setprecision(9)<<solve(n,m)*a<<endl; 28 return 0; 29 } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/GreenDuck/p/10799543.html

總結(jié)

以上是生活随笔為你收集整理的19_05_01校内训练[polygon]的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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