binary search precision problem on double[Please help]

Правка en1, от acash, 2020-05-30 17:32:14

Lanterns Problem Please forgive me if my ques is not good i am not good at it I am getting precision error on it Test case was huge so i was not able to debug. Mentioned in Prob absolute or relative error doesn't exceed 10 - 9.

example wrong answer 1st numbers differ - expected: '22258199.5000000', found: '22258200.0000000', error = '0.0000000'

#include<bits/stdc++.h>
using namespace std;
#define int long long
vector<double>a;
double eps = 1e-9;
bool check(double s,double dist){
    if(a[0]-s>eps)return false;
    if(dist-a.back()-s>eps)return false;
    for(int i=1;i<((int)a.size());i++){
        if(abs(a[i]-a[i-1])-2*s>eps){
            return false;
        }
    }
    return true;
}
int32_t main(){
    int n,d;
    cin>>n>>d;
    a.resize(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    sort(a.begin(),a.end());
   // for(auto p : a)cout<<p<<endl;
    //exit(0);
    double low=0;
    double high=d;
    int iter=200;
    while(iter--){
        double mid=(low+high)/2;
        if(check(mid,d)){
            high=mid;
        }else low=mid;
    }
    cout<<low<<endl;

}

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский acash 2020-05-30 17:32:14 1267 Initial revision (published)