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.
11529  Strange Tax Calculation
Moderator: Board moderators
11529  Strange Tax Calculation
Last edited by baodog on Wed Oct 22, 2008 8:15 am, edited 1 time in total.
Re: 11529 Special Tax
There's a nonrandom O(n^2logn) algorithm.
ADD: I also tried random algorithm, but couldn't get AC.
Didn't have enough accuracy.

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

Rio
Re: 11529 Special Tax
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.
Some triangles can contain other triangles, but they may not. All triangles
can overlap but not be inside each other.

 Online Contest Administrator
 Posts: 20
 Joined: Fri Nov 30, 2001 2:00 am
Re: 11529 Special Tax
Don't try to count how many point each triangle contains.
Select a point and try to determine how many triangles it is within.
Select a point and try to determine how many triangles it is within.
Re: 11529 Special Tax
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
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
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...
I'm getting WA in 7 seconds though...
Re: 11529 Special Tax
Hi,
I still cannot figure out how the circular sweepline can do the job in O(nlogn).
I still cannot figure out how the circular sweepline can do the job in O(nlogn).
Re: 11529 Special Tax
I guess using DP will result in O(nlogn) to find the number of triangles contain a specific point