877 - Offset Polygons

[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]

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".

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......

[little joey]

I printed -0.000

Thanks Observer; got AC after changing this detail.

[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)

[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]

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);