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