Codeforces and Polygon may be unavailable from December 6, 19:00 (UTC) to December 6, 21:00 (UTC) due to technical maintenance. ×

DontLookBack's blog

By DontLookBack, history, 4 years ago, In English

This problem : https://mirror.codeforces.com/problemset/problem/514/B, gives different verdicts according to different change in epsilon values used for comparing two double quantities. Why is this so? For example it passes for epsilon from 1e-9 to 1e-13.

During contest how am I supposed to know which epsilon value will pass?

Solution:


#include <bits/stdc++.h> using namespace std; #define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define ll long long #define ld long double #define all(v) v.begin(),v.end() #define ff first #define ss second #define pb push_back #define mp make_pair #define pi pair<int,int> const ll maxn=1e3+50; const ll mod=1e9+7; const double epsilon=1e-12; bool deq(double a, double b) { return std::abs(a - b) < epsilon; } int main() { fast; int n,x,y,u,v,i,j; cin>>n>>x>>y; pi p[n]; for(i=0;i<n;i++){ cin>>u>>v; p[i]={u,v}; } bool mark[n]; memset(mark,false,sizeof(mark)); int ans=0; for(i=0;i<n;i++){ if(mark[i]) continue; double del,f=0; if((x-p[i].ff)!=0) del=(1.0*(y-p[i].ss))/(x-p[i].ff); else{ f=1; } for(j=i;j<n;j++){ if(mark[j]) continue; if((x-p[j].ff)!=0){ if(deq(del,(1.0*(y-p[j].ss))/(x-p[j].ff))) mark[j]=true; } else if(f) mark[j]=true; } ++ans; } cout<<ans; }

Please dont downvote unnecessarily.

Any help will be appreciated.

Full text and comments »

  • Vote: I like it
  • +3
  • Vote: I do not like it