UVA - 12097 Pie

本文主要是介绍UVA - 12097 Pie，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：有F+1个人来分N个圆派，每个人得到的必须是一整块派，而不是几块拼在一起，且面积要相同，求每个人最多能得到多大面积的派（不必是圆形）

思路：二分答案，因为派是不能拼起来的，所以一个半径r的派只能切出[pir^2/x]个派。向下取整，

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int MAXN = 10005;
const double PI = acos(-1.0);int n,f;
double A[MAXN];bool ok(double area){int sum = 0;for (int i = 0; i < n; i++)sum += floor(A[i]/area);return sum >= f+1;
}int main(){int t;scanf("%d",&t);while (t--){scanf("%d%d",&n,&f);double Max = -1;for (int i = 0; i < n; i++){int r;scanf("%d",&r);A[i] = PI*r*r;Max = max(Max,A[i]);}double L = 0,R = Max;while (R - L > 1e-5){double M = (L+R)/2;if (ok(M))L = M;else R = M;}printf("%.4lf\n",L);}return 0;
}

这篇关于UVA - 12097 Pie的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---