Page 1 of 1

11529 - Strange Tax Calculation

Posted: Tue Oct 21, 2008 12:46 am
by 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.

Re: 11529 Special Tax

Posted: Tue Oct 21, 2008 2:11 am
by 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

Re: 11529 Special Tax

Posted: Tue Oct 21, 2008 2:51 am
by 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.

Re: 11529 Special Tax

Posted: Tue Oct 21, 2008 4:09 am
by 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.

Re: 11529 Special Tax

Posted: Tue Oct 21, 2008 4:25 am
by 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

Re: 11529 Special Tax

Posted: Tue Oct 21, 2008 4:35 am
by 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...

Re: 11529 Special Tax

Posted: Tue Oct 28, 2008 7:45 am
by lyhung
Hi,

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

Re: 11529 Special Tax

Posted: Fri Nov 07, 2008 9:25 am
by lyhung
I guess using DP will result in O(nlogn) to find the number of triangles contain a specific point