11277 - Cyclic Polygons

[tobby]

I get WA. I try finding circumradius by bisection. I fear that it may not be so accurate for some cases, like very thin triangles. Can anyone give me some test cases? Thank you.

[sclo]

There are 2 cases:
The center of circle can lie inside the polygon or outside.
The bisection method is slightly different for these 2 cases.

[tobby]

I also take two cases as you said. What epsilons do you use?

[sclo]

I didn't use any epsilon
I just iterate the bisection 100 times.

Also, instead of bisection on radius r, I did bisection on 1/r, because r can range from xmax/2 to infinity.

r = infinity is the degenerate case, and output 0.000 there.

[tobby]

Thanks. I get accepted.

[baodog]

I recommend Newton's method for this
problem.

Although bisection code will also run in time.
The combinatorial nature of the problem is to
realize you can re-order the edges to your advantage...
Think about how you can re-order the edges to make
your code significantly faster (amortized).

[liuctic]

The input data does not contain cases that the center of the circle lies out of the polygon.

[baodog]

I will add some datasets where the
center lies outside the polygon and
the problem will be rejudged.

What happened is the dataset was generated using
randomization. Somehow it didn't hit that
case as I had thought it surely would.

[tobby]

Don't add too much cases la, since many accepted solutions are close to time limit.. I think a couple of new cases is enough.