I solved a problem recently using floating point arithmetic. I suspect the solution should not work for some test case because of floating point precision errors, but cannot find a case where it would fail. Moreover, the solution gets "Accepted" verdict.↵
↵
Link to the submission (Codeforces Round #660 E): [submission:89366718]↵
↵
The submission is an implementation of the Convex Hull Trick approach mentioned in the [editorial](https://codeforces.com/blog/entry/80828) of the problem.↵
↵
If you look through the code, you will find that I have maintained forbidden ranges of cotangents of an angle and then iterate over the critical angles (i.e. extremeties of some range of forbidden angles, which are not forbidden themselves).↵
↵
I suspect that `float(xr[j] - xl[i]) / (y[i] - y[j])` should return unequal values for some mathematically equal fractions (like $5/3$ and $15/9$) because of precision errors.↵
↵
In such case, let's say there are two ranges $\[a, b\]$ and $\[c, d\]$ with $b = c$ (mathematically). In such a case a possible value that is not forbidden is $b$. This obviously will not work if there are precision errors which make the calculated values of $b$ and $c$ such that $b$ is slightly greater $c$. Then, $b$ will become part of a forbidden range.↵
↵
My question is, does the above case not show up in the test cases of the problem or is the floating point arithmeticI talked about guaranteed to be exact?in my code guaranteed to be exact because of some reason?↵
↵
Can you suggest a case where the program would break?↵
↵
The following program shows though that the precision errors I mentioned do occur:↵
↵
~~~~~↵
#include <cassert>↵
#include <iomanip>↵
#include <iostream>↵
#include <random>↵
using namespace std;↵
↵
float foo (int n, int d, int c)↵
{↵
return float(n * c) / (d * c);↵
}↵
↵
int main()↵
{↵
default_random_engine generator;↵
uniform_int_distribution<> dist(1, 10000);↵
while(true)↵
{↵
int n = dist(generator), d = dist(generator), c1 = dist(generator), c2 = dist(generator);↵
float f1 = foo(n, d, c1), f2 = foo(n, d, c2);↵
cerr << "Testing with n=" << n << ", d=" << d << ", c1=" << c1 << ", c2=" << c2 << '\n';↵
cerr << fixed << setprecision(10) << "Received f1=" << f1 << " and f2=" << f2 << '\n';↵
assert(f1 == f2);↵
cerr << "OK\n";↵
}↵
}↵
~~~~~
↵
Link to the submission (Codeforces Round #660 E): [submission:89366718]↵
↵
The submission is an implementation of the Convex Hull Trick approach mentioned in the [editorial](https://codeforces.com/blog/entry/80828) of the problem.↵
↵
If you look through the code, you will find that I have maintained forbidden ranges of cotangents of an angle and then iterate over the critical angles (i.e. extremeties of some range of forbidden angles, which are not forbidden themselves).↵
↵
I suspect that `float(xr[j] - xl[i]) / (y[i] - y[j])` should return unequal values for some mathematically equal fractions (like $5/3$ and $15/9$) because of precision errors.↵
↵
In such case, let's say there are two ranges $\[a, b\]$ and $\[c, d\]$ with $b = c$ (mathematically). In such a case a possible value that is not forbidden is $b$. This obviously will not work if there are precision errors which make the calculated values of $b$ and $c$ such that $b$ is slightly greater $c$. Then, $b$ will become part of a forbidden range.↵
↵
My question is, does the above case not show up in the test cases of the problem or is the floating point arithmetic
↵
Can you suggest a case where the program would break?↵
↵
The following program shows though that the precision errors I mentioned do occur:↵
↵
~~~~~↵
#include <cassert>↵
#include <iomanip>↵
#include <iostream>↵
#include <random>↵
using namespace std;↵
↵
float foo (int n, int d, int c)↵
{↵
return float(n * c) / (d * c);↵
}↵
↵
int main()↵
{↵
default_random_engine generator;↵
uniform_int_distribution<> dist(1, 10000);↵
while(true)↵
{↵
int n = dist(generator), d = dist(generator), c1 = dist(generator), c2 = dist(generator);↵
float f1 = foo(n, d, c1), f2 = foo(n, d, c2);↵
cerr << "Testing with n=" << n << ", d=" << d << ", c1=" << c1 << ", c2=" << c2 << '\n';↵
cerr << fixed << setprecision(10) << "Received f1=" << f1 << " and f2=" << f2 << '\n';↵
assert(f1 == f2);↵
cerr << "OK\n";↵
}↵
}↵
~~~~~
