OJ Board

The tournament method.

Picture an essentially complete binary tree with all elements at the leaves and at a node having the minimum of the elements at its sons.
Now where can the second min number be in this tree ?

Miguel Angel:
It's not very clear how your algorithm works.
But, yes - the line segments (of course?) can overlap.
And, yes - the greedy approch can be applied - if done in the right way.

Use the Gready approch.

The Kuhn-Munkres algorithm is for bipartite graphs only.
For general graphs try Edmonds primal-dual algorithm.

No, DP doesn't lead to a good solution.
Instead, a sweep-style algorithm is needed.
Aim at an O(n^2) time algorithm.

WARNING : Spoiler follows:








Consider the largest empty rectangle.
There are two cases:
1) Left edge is the left border of the forest.
2) There is a tree on the left edge ...

try realloc()

Yarin: What do you mean by "complexity doesn't matter on input size" ?
Anyway, the reference:
Hisao Tamaki and Takeshi Tokuyama.
Algorithms for the maxium subarray problem based on matrix multiplication.
In Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms,
pages 446-452 ...

Actually there is a faster algorithm than O(n^3).
There was one in a siam journal some years ago.
It will probably not be faster on input sizes considered here, though.

Ok, I asked because you said you added up for each missile.
When I did this problem I succeeded first time with just this standard piece of code
for detecting hits.

[c]
int lefton(point *a, point *b, point *c)
{
return (b->x - a->x)*(c->y - a->y) - (c->x - a->x)*(b->y - a->y) >= 0;
}

int ...

What if a kingdom is struck more than once ?

you get integer overflow

You miss the last turn,

try: Kristoffer Hansen

Change these line
[cpp]
while (cin)
{
cin >> N;
[/cpp]

to

[cpp]
while (cin >> N)
[/cpp]

oops, should have read the description again. Just relied on my vague memory ...

Also, the graph need not to be connected. So one may need to start the recursion several times.