1 / 2
Apr 2023

problem link: https://www.spoj.com/problems/PIE/14
code screenshot: https://vjudge.net/solution/snapshot/4198257810

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;}
  • created

    Apr '23
  • last reply

    Apr '23
  • 1

    reply

  • 552

    views

  • 2

    users

  • 2

    links

Well, what happens if you change it? Do you lose precision in the answer?