ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1426. Rectangles

accurace question
Posted by svr 29 Nov 2007 10:39
How must we verify that
integer point (m,n) belongs to
double segment (x1,y1)-(x2,y2) if
precision equals to 10^-6.
Re: accurace question
Posted by svr 29 Nov 2007 11:12
Also:
How to verify that double points (x1,y1) and (x2,y2)
are different?
Using ((x1-x2!=0)||(y1-y2!=0)) or
((fabs(x1-x2)>1.e-6)||(fabs(y1-y2)>1.e-6))
I think that value 1e-6 has no information.
Most probable situation that for answer given by
program checker verifing all conditions with
maximal possible precision 1e-16.

Edited by author 29.11.2007 20:54
Re: accurace question
Posted by Alias (Alexander Prudaev) 29 Nov 2007 19:54
sqrt(sqr(x1-x2) + sqr(y1-y2)) < 1e-6
Re: accurace question
Posted by svr 29 Nov 2007 23:31
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