877 - Offset Polygons

All about problems in Volume 8. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

877 - Offset Polygons

Post by little joey »

Although this looks like an easy problem, I fail to get AC (as many others, looking at the stats).

My approach is simple:
- shift all edges offset to the left;
- calculate the intersections of the shifted edges.
This means that the new polygon always has the same number of edges/vertices as the old one. I print the co-ordinates with three digits after the decimal dot.

Anything I overlooked? Or is it simply a matter of precision? Without the proper output specification, I think this problem should have a special corrector.

BTW, I assume that the input follows the input description (max. 8 vertices, min. 3, clockwise, convex, etc.) without checking or correcting.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer »

Hi,

I can tell you that the judge uses exactly the same algorithm as yours, little joey. Nearly all the test cases are hand-made, so they should fit the problem description correctly.

Make sure that your program doesn't print "-0.000". :wink:

P.S. I can see that Anton Maydell got AC by no more than 2 submissions. :-)

P.S.2 If you still experience problems, please consider sending me your code, and let me see if the mistake is on my side......
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey »

I printed -0.000 :oops:

Thanks Observer; got AC after changing this detail.

zid_adrenalyns
New poster
Posts: 11
Joined: Thu Jun 15, 2006 5:46 pm
Location: Juchitán Oaxaca, México
Contact:

877 Precision Error???

Post by zid_adrenalyns »

hi little joey, I proposed a similar solution as yours, but I can't got AC. Can you post I/O samples? Because I think that i have an precision error.

I can't understand how you can print "-0.000"????

(sorry about my "rusty" english)
Making simple things simple, making complex things possible!!

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey »

Printing "-0.000" is a 'feature' of the gcc compilers. If a float or double is close to 0, but on the negative side of it, printf() will print a leading minius.
If your value of zero is the result of (a long series) of calculations, then it can get imprecise; even if the true value is 0 exactly, the actual value can be a very small negative number, and then your program accidentally prints "-0.000".
The cure is to add a small number (say 1e-8) to anything you print. Another method is to first print to string, and then remove the minus from the string before printing.

zid_adrenalyns
New poster
Posts: 11
Joined: Thu Jun 15, 2006 5:46 pm
Location: Juchitán Oaxaca, México
Contact:

I GOT AC, thanks little joey

Post by zid_adrenalyns »

WA code:
printf ("%.3f %.3lf\n",p_inter.x,p_inter.y);

AC code:
printf ("%.3f %.3lf\n",p_inter.x+1e-8,p_inter.y+1e-8);

:)
Making simple things simple, making complex things possible!!

Post Reply

Return to “Volume 8 (800-899)”