OJ Board

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.

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

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.

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

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

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

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

Hi,

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

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