【poj3122】 Pie

http://poj.org/problem?id=3122 (题目链接)

题意

  给出N个pie的半径和F个friend,每个friend得到的pie必须一样,求每个人能得到的pie的最大大小。

solution

  经典二分答案。

代码

// poj3122
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
#define inf 2147483640
#define Pi acos(-1.0)
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
using namespace std; int n,f,r[1000010];
double a[1000010]; bool ok(double m) {
int sum=0;
for (int i=1;i<=n;i++) sum+=floor(a[i]/m);
return sum>=f+1;
}
int main() {
int T;
scanf("%d",&T);
while (T--) {
scanf("%d%d",&n,&f);
double maxl=-1;
for (int i=1;i<=n;i++) {
scanf("%d",&r[i]),a[i]=r[i]*r[i]*Pi;
maxl=max(maxl,a[i]);
}
double l=0.0,r=maxl;
while (r-l>1e-5) {
double mid=(l+r)/2;
if (ok(mid)) l=mid;
else r=mid;
}
printf("%.4lf\n",l);
}
return 0;
}

  

上一篇:pygame 练习之 PIE game (以及简单图形训练)


下一篇:Pizza Pie Charts – 基于 Snap SVG 框架的响应式饼图