|
|
Show all threads Hide all threads Show all messages Hide all messages | I tried solve this problem 10 days!!!! AC!!!!!! | xurshid_n | 1426. Rectangles | 7 Feb 2012 13:10 | 1 | Very nice problem. Thanks to authors. Upsa!! 0.031s !!!!! Edited by author 07.02.2012 17:27 | Русское условие задачи. | Yermak | 1426. Rectangles | 20 Aug 2008 16:20 | 1 | Почему буква 'Ё' везде в условии пишется как 'Ё', а в слове "ковёр" - как 'Е'? Нехорошо. И да, в последнем предложении вступления первая запятая лишняя! Edited by author 20.08.2008 16:25 | accurace question | svr | 1426. Rectangles | 29 Nov 2007 23:31 | 4 | How must we verify that integer point (m,n) belongs to double segment (x1,y1)-(x2,y2) if precision equals to 10^-6. 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 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 | WA #7 !! | Abbas Mehrabian | 1426. Rectangles | 20 Sep 2006 00:56 | 1 | WA #7 !! Abbas Mehrabian 20 Sep 2006 00:56 and now i pass all the tests but test #7! Is that a matter of accuracy? I got tired of trying this problem !! | WA on test 4 help! Any tricks? | Zhu Chenguang | 1426. Rectangles | 9 Aug 2006 14:05 | 3 | I got WA on 4-th many times. Than I replaced 4 digits after . to 14 digits, and got AC immediately 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? |
|
|
|