首页 > 代码库 > LA3635 Pie (二分法)
LA3635 Pie (二分法)
链接：http://vjudge.net/problem/33697
分析：二分答案。假设每个人得到派的最大面积是x，判断是否能满足F+1个人（因为派是不可以拼起来的，所以一个半径为r的派只能切出[πr²/x]个派，其他部分就浪费了）。
1 #include <cstdio> 2 #include <cmath> 3 #include <algorithm> 4 using namespace std; 5 6 const double PI = acos(-1.0); 7 const int maxn = 10000 + 5; 8 9 int n, f;10 double A[maxn];11 12 bool ok(double area) {13 int sum = 0;14 for (int i = 0; i < n; i++) sum += floor(A[i] / area);15 return sum >= f + 1;16 }17 18 int main() {19 int T;20 scanf("%d", &T);21 while (T--) {22 scanf("%d%d", &n, &f);23 double maxa = -1;24 for (int i = 0; i < n; i++) {25 int r; scanf("%d", &r);26 A[i] = PI * r * r;27 maxa = max(maxa, A[i]);28 }29 double L = 0, R = maxa;30 while (R - L > 1e-5) {31 double M = (L + R) / 2;32 if (ok(M)) L = M;33 else R = M;34 }35 printf("%.4lf\n", L);36 }37 return 0;38 }
LA3635 Pie (二分法)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。