|
|
back to boardaccurace 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 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 |
|
|