OJ Board

sclo wrote:In my case, the epsilon is 1e-7, but 0.0009 is way too big. I would never use any epsilon larger than 1e-6.

More about my method: I treated the case there're 2 adjacent sides parallel as special cases. The sample input doesn't have that case. It is possible that 2 adjacent sides are parallel if we keep removing sides. Also, if we use the O(n^4) algorithm of choosing every 3 sides, this case would also appear.

If you perturbate the points then no two sides of the polygon will parallel and maximum value of R won't change too much if the perturbation is small.

Robert Gerbicz wrote:

sclo wrote:In my case, the epsilon is 1e-7, but 0.0009 is way too big. I would never use any epsilon larger than 1e-6.

More about my method: I treated the case there're 2 adjacent sides parallel as special cases. The sample input doesn't have that case. It is possible that 2 adjacent sides are parallel if we keep removing sides. Also, if we use the O(n^4) algorithm of choosing every 3 sides, this case would also appear.

If you perturbate the points then no two sides of the polygon will parallel and maximum value of R won't change too much if the perturbation is small.

The way that I implement it would be quite sensitive to pertubations, since the problem was division by zero. There is a way around it though.
Well think of it this way:
1/0+ -> inf, but 1/0- -> -inf, but whether it is 0+ or 0- depends on the pertubation itself. Rewriting the formulas would be a way to remove this error, since the structure of the problem should not be sensitive to input data.

By the way, this problem is reducible to the problem of finding the radius of inscribed circle for a triangle.

1. I used epsilon of 1e-5 for the ternary search (and epsilon of 1e-8 for
the geometry stuff). By the way 1e-4 gives WA.

2. The search interval for x is from min_x to max_x of the polygon.
For a "fixed" x the serch interval for y is from min_y to max_y - where
min_y is is the y coordinate of the lowest point of intersection between
the vertical line x and the sides of the polygon and max_y is the y
coordinate of the hightest point of intersection between the vertical
line x and the sides of the polygon. Now you don't have to check for
point in polygon.

Hello, i would like to implement the sclo approach... but i cant realise a nice algorithm to get the angle bisectors... would anyone please give me a pseudo code, hint or some page to read about??... do anyone knows a good book of computational geometry?? thanks. eric.

A nice fact from analytic geometry: (signed) distance from line ax+by+c=0 to point (x0, y0) is (a x0 + b y0 + c) / sqrt(a^2 + b^2). The sign of the expression is + or -, depending on which half-plane the point is in.

Angular bisector is the locus of points equidistant from the two lines, so you could write line equations for two adjacent sides, normalize them, and then the bisector equation will be just a1 x + b1 y + c1 = a2 x + b2 y + c2.

Here's my method for finding angle bisectors:
Suppose we have triangle with vertices A,B,C and we want to find angle bisector of A:
We know that 2 points define a line, one of the point on the angle bisector is of course A.
The other point is (abs(A-B)*(C-A)/abs(C-A)+A+B)/2

where abs(P) is sqrt(P.x*P.x+p.y*P.y)

In other words, the second point is the midpoint of a line segment, where one end of it is B, and the other end is a point on the line AC that is distance abs(A-B) from A.

Although it is not immediately obvious, this method is equivalent to mf's method.

Thanks mf and sclo for their descriptions. I have one question for Simon:

sclo wrote:More about my method: I treated the case there're 2 adjacent sides parallel as special cases. The sample input doesn't have that case. It is possible that 2 adjacent sides are parallel if we keep removing sides.

Can you give a sample polygon where this happens? My program doesn't explicitly handle such cases, but still gets accepted (but maybe it implicitly deals with them).

little joey wrote:Thanks mf and sclo for their descriptions. I have one question for Simon:

sclo wrote:More about my method: I treated the case there're 2 adjacent sides parallel as special cases. The sample input doesn't have that case. It is possible that 2 adjacent sides are parallel if we keep removing sides.

Can you give a sample polygon where this happens? My program doesn't explicitly handle such cases, but still gets accepted (but maybe it implicitly deals with them).

Removing a side from a square creates such a case.
Here's what I do:
At every step of my algorithm, keep a linked list of the remaining sides of the input polygon.
For every 3 adjacent sides for the current polygon, compute the radius by computing intersection of angle bisectors.
Initially, the parallel case won't appear.
Then, I pick the minimum computed radius, and delete the middle side from the current polygon. This has the effect of shrinking the current polygon as in mf's method.
Next, update some radius since I removed a side, and repeatedly pick the minimum radius.
Repeat until there are only 3 sides left. The final computed radius is the solution.

OK, I see.
This won't happen in my method, because after determining the minimum radius in a certain step, I remove _all_ the sides for which the intersection of the angle bisectors lie at that minimum radius in one action. This means that in case of a square, the minimum radius is determined once and then all four sides are deleted, leaving a polygon with zero vertices (which means I'm done).