OJ Board

Hi gush,
You don't have to actually store all pairs first before processing them.
If you make sure you generate them in the sorted order (first by increasing x, then increasing y), you can directly 'insert' them while you generate them. Inserting, in the terms of Skiena, meaning maintaining an ...

OK, I finaly got it using the algorithm mentioned by Skiena.

For the case above, my program takes 5 or 2 seconds, dependent on the order in which you compare the strings, which is about 10 and 4 seconds on the judge, resp.

So we may safely assume that the judges input doesn't contain such 'horror ...

I got Accepted with an O(p*(n-p)) Algorithm, where p is length of LCS. I found this algorithm in a paper with the subject: "A New Flexible Algorithm for the Longest Common Subsequence Problem".
But I think there must exist a better algorithm for this specific problem, maybe you can use the ...

OK, I finaly got it using the algorithm mentioned by Skiena.

For the case above, my program takes 5 or 2 seconds, dependent on the order in which you compare the strings, which is about 10 and 4 seconds on the judge, resp.

So we may safely assume that the judges input doesn't contain such 'horror ...

has this problem been fixed yet?

ok

All the points are on the same circle. So there should be no 3 points in the same line.

This is my answer:
....
I've tested that the distances between them are integers. But I still got WA. Why?

the output should be as follows.

WINNING
3
LOSING

WINNING
3
WINNING
1 12 15 17 20 24 28 31 33 36 47
WINNING
3 5
WINNING
4 10 16 22 23 33 34 35 37 38 39 49 50 51
WINNING
17 20
WINNING
1 4 5 6 9
WINNING
3 6
WINNING
3
WINNING
11
WINNING
12
WINNING
3 12
WINNING
13 16
LOSING

WINNING
12 15
WINNING
11 ...

the output should be as follows.

WINNING
3
LOSING

WINNING
3
WINNING
1 12 15 17 20 24 28 31 33 36 47
WINNING
3 5
WINNING
4 10 16 22 23 33 34 35 37 38 39 49 50 51
WINNING
17 20
WINNING
1 4 5 6 9
WINNING
3 6
WINNING
3
WINNING
11
WINNING
12
WINNING
3 12
WINNING
13 16
LOSING

WINNING
12 15
WINNING
11 ...

just use DFS

color[z] must be defferent from color[z + 1] and
color[z + 1] should be the same as color

thus, we can use 3-dim array to store the data.
D[a][l] : form a to b, the len of the last seg clicked out is l, and of course the color of the seg is color.

Per, could you please tell us how to solve this problem efficiently? I can't avoid TLE.