any SPOJ users?

[bbi5291]

saltpro15 @ Wed Aug 26, 2009 9:31 pm wrote:

umm, don't all algorithms have to be looked up? Or does stuff like Dijkstra's just pop into code gurus heads?

Touche. What I meant is that I was impressed that he knew this algorithm before having read this problem (that is, he looked it up before.)

@ Analysis Mode: You overestimate random passersby
And no, I have never coded this algorithm, and it's really too difficult even for IOI level so it'll be a while before I get around to coding it. I mean, it's not in the Algorithms text by Sedgewick, even.

(Edit: this forum doesn't accept e with an acute accent on it >.<)

[saltpro15]

ah I see. btw has anyone taken a look at that new SPOJ problem about determining points in a triangle?

[bbi5291]

It would be quite trivial if the third vertex of the triangle was guaranteed to be on a lattice point (Pick's theorem), but as it isn't, things get a bit more complicated. I'll work on it...

[A.J]

@Brian - Alas, this algorithm floats above the realm of my capability...but one day I intend on using it.

@saltpro15 - what is the problem code?

[bbi5291]

http://www.spoj.pl/submit/GPINTRI

[Cyril]

I've got an okay heuristic solution for that GPINTRI problem- I don't know if it'll handle T = 100000.

But, first, Mr. Mode, I don't see enough of a problem with my wording to be singled out.

At least floor(b/a) x increments are needed for one y increment, so a straightforward walk along the line, sort of like the circle-walking in Project Euler 210, should suffice. That's the somewhat obvious algorithm for this, but here's a heuristic.

Let N = the point (n, an/b), which is the third vertex of the triangle.
Let O = the origin.

Find the point L = the last lattice point on y = ax/b that before N. Drop a perpendicular to the x-axis: call this L'.
Find the point P = the first lattice point on y = ax/b after N. Likewise, P'.
Decide on whether L or P is closer to N.

If L is closer, use Pick's theorem to find the number of points in OLL'. If P is closer, same thing for OPP'.

In either case, you're left with a quadrilateral composed of a rectangle and a right triangle. After chopping away that rectangle, run the incremental walking thing on that annoying remaining non-lattice point triangle.

I'll do it later- I'm hungry.

[A.J]

hey Cyril, the PE problem comes out tomorrow morning at 8 AM (our time). Are you going to attempt it then?

[bbi5291]

You guys are in a different time zone?

[A.J]

No, but I just wanted to say that it is 8 AM EDT, and not GMT.

[Analysis Mode]

Cyril @ Thu Aug 27, 2009 10:16 am wrote:

But, first, Mr. Mode, I don't see enough of a problem with my wording to be singled out.

What are you talking about?

[saltpro15]

For you math people, I've found another interesting problem

[A.J]

I believe all we need for this problem is P.I.E (in more ways than one)

[Analysis Mode]

saltpro15 @ Thu Aug 27, 2009 8:28 pm wrote:

For you math people, I've found another interesting problem

Uh no, it's not a math problem. I seem to recall someone (I think it was Hanson or bbi5291) mentioning that voronoi diagrams are needed. Not at all trivial to code.

[A.J]

hmm...

Voronoi diagrams are useful when finding the largest circle in a set of points (or a polygon), but I think that might be jumping the gun here.

I believe that PIE is too inefficient for this problem, though I believe there are other ways to go about this problem apart from using voronoi diagrams.

[bbi5291]

I think PIE would have a worst-case time complexity close to O(2^n). That being said, I think a more sophisticated approach would be in order.
I posted a problem on the PEG Judge which required you to compute the perimeter of a union of circles. First we consider that problem.
We can find the perimeter of the entire union by determining what amount of perimeter is contributed by each circle. To this end, we consider each circle in turn, and use line sweep. The details are left to you, of course. (If you want to code it, feel free to request an account on the PEG judge; the problem is called "detectors".)

It turns out we can do the same with area. Consider the general case of two intersecting circles (that is, they are not tangent). If we draw a line through the two points of intersection, this divides the union of the two circles into two segments! Each segment "belongs" to one of the circles. If we add up the areas of the two segments, we get the area of the whole union!

In general what you can do is, for each circle, consider all possible lines drawn through two intersection points of this circle with another circle (it has to be the same circle for both points, if that wasn't clear). These lines fence off a "cell" which is "owned" by that circle. By adding the areas owned by each circle, you obtain the area of the circle union. As n = 50 at worst, there is room for some slack.

The reason I mentioned the Laguerre Voronoi diagram (also called a power diagram, although the latter may be more general) is because computing it solves this problem (almost, you still have to find the area of the intersection of each circle with its cell). Define the Laguerre distance of point P from circle C with center O and radius r to be sqrt(d^2 - r^2) where d is the Euclidean distance from P to O. (When P is outside C, this is the length of the tangent from P to C; this is trivial to prove with that well-known theorem whose name seems to be a subject of disagreement.)

Now the Laguerre Voronoi diagram is constructed similarly to the Voronoi diagram, except that now the distance metric used is the Laguerre one. Incredibly, Laguerre cells are still convex polygons (or polyhedra, in the more general case of higher dimensions) and, for a given pair of intersecting circles, there is a line (or line segment, or ray) in the Laguerre Voronoi diagram that passes through their points of intersection; if they are disjoint, the corresponding line is outside both circles. The proof is left as an exercise for the reader.