題目大意是要辦生日Party,有n個餡餅,有f個朋友,接下來是n個餡餅的半徑。然後是分餡餅了, 注意咯自己也要,大家都要一樣大,形狀沒什麼要求,但都要是一整塊的那種,也就是說不能從兩個餅中 各割一小塊來湊一塊,像面積為10的和6的兩塊餅(餅的厚度是1,所以面積和體積相等), 如果每人分到面積為5,則10分兩塊,6切成5,夠分3個人,如果每人6,則只能分兩個了! 題目要求我們分到的餅盡可能的大! 只要注意精度問題就可以了,一般WA 都是精度問題
運用2分搜索:
首先用總餅的體積除以總人數,得到每個人最大可以得到的V,但是每個人手中不能有兩片或多片拼成的一塊餅,
最多只能有一片分割過得餅。用2分搜索時,把0設為left,把V 設為right。mid=(left+right)/2;
搜索條件是:以mid為標志,如果每塊餅都可以分割出一個mid,那麼返回true,說明每個人可以得到的餅的體積可以
大於等於mid;如果不能分出這麼多的mid,那麼返回false,說明每個人可以得到餅的體積小於等於mid。
(1)精度為:0.000001
(2) pi 用反余弦求出,精度更高。
#include#include #include using namespace std; double pi = acos(-1.0); int F,N; double V[10001]; bool test(double x){ int num=0; for(int i=0;i =F) return true; else return false; } int main() { int t,r; double v,max,left,right,mid; scanf("%d",&t); while(t--){ scanf("%d%d",&N,&F); F = F + 1; for(int i=0;i 1e-6){ mid = (left + right) / 2; if(test(mid)) left = mid; else right = mid; } printf("%.4lf\n",mid); } return 0; }