## 11529 - Strange Tax Calculation

Moderator: Board moderators

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

### 11529 - Strange Tax Calculation

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.
Last edited by baodog on Wed Oct 22, 2008 8:15 am, edited 1 time in total.

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

### Re: 11529 Special Tax

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
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

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

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

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

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

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

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

lyhung
New poster
Posts: 7
Joined: Tue Oct 28, 2008 7:20 am

### Re: 11529 Special Tax

Hi,

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

lyhung
New poster
Posts: 7
Joined: Tue Oct 28, 2008 7:20 am

### Re: 11529 Special Tax

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