problem link: https://www.spoj.com/problems/PIE/
code screenshot: https://vjudge.net/solution/snapshot/41982578
Today I try to solve the PIE-pie problem. But at first I don’t understand how to approach the solution.
So I get some idea from other’s solution. Now I understand all the solution and the approach except the base condition of the binary search. Why the base condition was 1e-6 instead of 1?
Please help me…
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pb push_back
ll n,f,input;
std::vector<ll> v;
bool possible(double size){
ll totalCake=0;
for(ll i=0; i<n; i++){
totalCake+=((v[i]*v[i])*M_PI)/size;
}
return totalCake>=f;
}
int main(){
fast;
#ifndef ONLINE_JUDGE
freopen("inputf.in","r",stdin);
freopen("outputf.out","w",stdout);
#endif
////////////////////////////////
int t;
cin>>t;
while(t--){
v.empty();
cin>>n>>f;
f++;
int temp=n;
while(temp--){
cin>>input;
v.pb(input);
}
sort(v.rbegin(), v.rend());
double maxV=(v[0]*v[0])*M_PI;
double low=0, high=maxV, mid;
while(high-low>=1e-6){
mid=(high+low)/2;
if(possible(mid))low=mid;
else high=mid;
}
if(possible(high))cout<<high<<endl;
else cout<<low<<endl;
}
return 0;}
