11529 - Strange Tax Calculation

[baodog]

Hi,

I pick random 25000 random triangles, and use a really good random number generator
that can generate 1 million random numbers with no problem, but still get WA!

Help is really appreciated. I tried many submissions, brute forcing small cases,
and difference seeds for my random number generator.

[rio]

There's a non-random O(n^2logn) algorithm.

ADD: I also tried random algorithm, but couldn't get AC.
Didn't have enough accuracy.
----
Rio

[baodog]

How is O(n^2 lgn) possible ? It takes O(n^3) to enumerate all the triangles.
Some triangles can contain other triangles, but they may not. All triangles
can overlap but not be inside each other.

[contest_clarificator]

Don't try to count how many point each triangle contains.

Select a point and try to determine how many triangles it is within.

[rio]

There's no need to enumerate through all O(n^3) triangles.

Hint: Given one point, think about how many triangles includes this point.
If this could be done in O(nlogn), the whole calculation could be done with O(n^2logn).
-----
Rio

[baodog]

Thanks! I do a circular line sweep from each point, it takes O(n lg n) for each point.

I'm getting WA in 7 seconds though...

[lyhung]

Hi,

I still cannot figure out how the circular sweepline can do the job in O(nlogn).

[lyhung]

I guess using DP will result in O(nlogn) to find the number of triangles contain a specific point