Don’t recognize what base condition should I use in Binary Search for this PIE problem from SPOJ.

Правка en1, от rahimuj570, 2023-04-05 14:42:10

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;}
Теги spoj, help me, binary search, cpp, c++, spoj problem, #binary search, pie, just for help, help, need help, #learning

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский rahimuj570 2023-04-05 14:42:10 1907 Initial revision (published)