NEED_HELP
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…
my code:
#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;
//======>> HERE'S THE CONFUSION ↓
//=====↓↓↓
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;}
Okay, suppose this. For some test case the correct answer is
10.577215
(approximately). Now, let's say your binary search has determined with a few iterations thatlow = 10.2
andhigh = 11.1
. If the breaking condition waswhile (high - low >= 1)
the binary search would quit here because11.1 - 10.2 = 0.9 < 1
. Now, the code would determine that the valuehigh
is bad and it would outputlow
.Notice that the difference between the correct answer
ans = 10.577215
and your answerlow = 10.2
is10.577215 - 10.2 = 0.377215
. According to the problem statement, your answer will be regarded correct if and only if the difference between your answer and the correct answer is at most10^-3 = 0.001
. It should be quite clear that the answer10.2
is not close enough to the correct one and you would get WA.You might think why isn't the condition then just
while (high - low >= 1e-3)
? This can sometimes still round incorrectly and you should always play it safe by doingwhile (high - low >= 1e-4)
at least (i.e. make it at least 1 digit more precise than what was asked). It doesn't really hurt the performance of the code even if the condition is more strict than required but most importantly, you will definitely not get WA due to precision errors.