11004 - Changing Roadmap

[Jon]

i got time limit.
i just calculate the value of k for each given point
for every i and j (i<j) by using given equation.then
check if k<0 and increment count.then at last print
the value of count.
so why time limit?
need better process?

[shalinmangar]

Yes, I used the same method.

But ofcourse the max values of N = 3000 and PP = 100, hence this method gives a complexity of O(n*n*PP) which is too slow to execute within the 3 second time limit.

[david]

Given an important point (x, y), k is negative for a pair of segments if and only if ai

[Darko]

I am not sure why I kept getting WA, is there anything else except the repeating points that is tricky in the input?

What I did was:
1. Get rid of duplicate points
2. For all lines, get the value of ax+by+c for all points (just if it is positive or negative)
3. For all points, count how many positives(p) and how many negatives (n) are there, if(p>1) add p*(p-1)/2 to the sum, same for n
4. Print out the sum

I used longs, I thought that should do it.

Darko

[valfiros]

I got TLE too...

I thought,
1. if A and B has same sign ,
2. K is minus in A + BK = 0.

but how can i upgrade my process from O(n^3) to O(n^2) or O(n)?

I used three loop ( n^2 * pp ) , but i couldn't find out more good algrothm.

Plsase suggest me something better


-JSKim@CAC wrote-

[helloneo]

I got TLE too...

I thought,
1. if A and B has same sign ,
2. K is minus in A + BK = 0.

but how can i upgrade my process from O(n^3) to O(n^2) or O(n)?

I used three loop ( n^2 * pp ) , but i couldn't find out more good algrothm.

Plsase suggest me something better


-JSKim@CAC wrote-

you know that n C 2 = n(n-1) / 2
don't need a loop to get it..

[shalinmangar]

Thanks that got me AC

[ivan.cu]

My algorithm not work.

For every PP (x, y):
I count the equations such that Ai*x+Bi*y+Ci < 0, be this count neg.
Increment the general result in neg*(neg - 1) / 2 and be pos = N - neg increment too in pos*(pos - 1) / 2.

That is now correct and don't occurs duplicate important places.

ivan

[Darko]

What I wrote above works. I just don't have that "remove duplicate points" part anymore. I don't remember what I changed to get AC, might have been something simple like using longs to count.

And read david's post, too.

[ivan.cu]

I assume that the equation need different sing for generate a roads for negative builder, that is obviously wrong, it need same sing.

Thank.