sqrt(sqr(x1-x2) + sqr(y1-y2)) < 1e-6

The problem optimized acording idea of combinatorical
optimization. In other words we must consider some finite
set of candidate to solution and verify each of them.
I applied continious optimization but understood that
must achive 1e-16 that TLE-impossible. Main combinatorial candidates is solutions wich has one common point with boundary of the picture.

P.S. Problem became much more simpler than i thought.
Values 5000 and 10000 connected so that if some rectangle
exists it can not intersect  picture boundary. Thus
enought to find good rectangle. It is not possible if one point is inside of other triangle but if it not the case
i think that good rectangle may have one side parallel to one of pairs of points and i can't find countexample.

AC  finally with 0.218c

All previous statements are right.
But precision question at the end became most delicate.
Numbers ~ 5000 very big and lead to round error so much that
double considarations with eps<1e-9 would incorrect.
I found eps=1e-9 experimentally using random tests.
But fact of impossibility I verified in integer way
without any eps and this way applicable to problem at hole.

P.S. To admins:
Make bound 20000 smaller for example as 15000 and you
will have exellent combinatorial geometry problem
for adults.

Edited by author 01.12.2007 09:28

Edited by author 01.12.2007 09:31

Why 4 digits after "."? Read problem statement carefully:

"The coordinates should be separated by single spaces and printed with at least SIX digits after decimal point"

Or initial problem statement has required 4 digits?