HDU1969

记得用PI=acos(-1)反三角函数求，用一次排序，然后二分和贪心

#include<iostream>
#include<algorithm>
#include<iomanip>
#include<cmath>
using namespace std;
class Pie{
public:
double r;
double s;
};
bool Check(Pie p[], int n, int f, double x);
bool Cpm(Pie&a, Pie&b){
return a.r>b.r;
}
int main(){
Pie p[10001];
int i, n, f, Case;
double left, right, mid, pi =acos(-1);
cin >> Case;
while (Case--){
cin >> n >> f;
f++;
for (i = 0; i < n; i++){
cin >> p[i].r;
p[i].s = p[i].r*p[i].r*pi; 
}
sort(p, p + n, Cpm); //按面积从小大大排序
left = 0.0, right = p[0].s; //左右边界
while (right - left>1e-5){
mid = (left + right)/2;
if (Check(p, n, f, mid))
left = mid;
else
right = mid;
}
cout <<setiosflags(ios::fixed)<<setprecision(4)<<(left+right)/2<< endl;
}
return 0;
}
bool Check(Pie p[],int n,int f, double x){//检查是否可以满足条件
int i = 0, peo = 0;
for (i = 0; i < n; i++){
peo += int(p[i].s / x);
if (peo >=f)
return 1;
}
return 0;
}