1003 - Can't Cut Down the Forest for the Trees

[datahaven]

Has anyone got any decent test data for this problem?

I'm getting WA and have no idea why! My code appears to work for all of the cases I've been able to come up with, but fails when I submit it.

These are all cases for which my code works properly:

Code: Select all

0 0 10 10 1 # Tree can't fall anywhere - 0 trees
5 5 2 7
0 0 10 10 1 # Tree intersects fence - 1 tree
5 5 2 6
0 0 10 10 2 # Two Trees, neither intersects fence - 2 trees
5 5 2 4
2 2 2 1
0 0 10 10 3 # Sample data - 2 trees
3 3 2 10
5 5 3 1
2 8 3 9
0 0 17 17 4 # Four trees - 4 trees
3 3 2 8
7 3 2 8
11 3 2 8
15 3 2 8
0 0 17 17 8 # Eight trees - 8 trees
3 3 2 8
7 3 2 8
11 3 2 8
15 3 2 8
3 7 2 8
7 7 2 8
11 7 2 8
15 7 2 8
0 0 17 17 8 # Eight trees - bottom row block top row - 0 trees
3 3 2 8
7 3 2 8
11 3 2 8
15 3 2 8
3 7 2 100
7 7 2 100
11 7 2 100
15 7 2 100
0 0 5 10 1 # Tree has room to fall (previous fp error case) - 1 trees
3 3 2 7
0 0 4 10 1 # Tree can only fall on fence - 0 trees
2 3 2 7
0 0 4 10 1 # Tree can only fall on fence - 0 trees (as before, other way up)
2 7 2 7
0 0 10 4 1 # As above, rotated 90d - 0 trees
7 2 2 7
0 0 10 4 1 # As above - 0 trees
7 7 2 7
0 0 20 20 9 # Touching in two places - 0 trees
5 5 2 40
9 5 2 40
4 8 2 40
7 8 2 4
10 8 2 40
5 12 2 40
9 12 2 40
5 15 2 40
9 15 2 40
0 0 0 0 0

(You'll need to write your input routines to ignore the # comments, or remove them before testing the file. I find allowing for comments handy for annotating test files, and it needn't require any changes to the input code if you write it well.)

I know these work because I've written code to draw the trees, chopped trees and fence as an svg file, which makes it much easier to check the results. I've also tested on randomly generated data with 100 trees, although this is a little harder to verify visually.

I've submitted identical versions of the code that differ only in whether a blank line appears after the final case, but get WA for both.

My suspicion is that my code is failing to properly handle cases where a chopped tree touches (rather than overlaps) another tree or the fence, but I've been unable to find a case where this seems to happen.

The question doesn't say that tree heights and diameters can't be zero or negative - I've assumed they can't.

Anyway, I'd appreciate any help anyone can offer. If you've yet to try this problem, give it a go - it's quite a fun one, especially if you write some code to draw out the trees. Hope my test data comes in handy if you do try it.

Adrian

[alcaide_redb]

I'm trying to solve the problem...do the trees fall down on a certain way?

[nVxx]

Can anybody point to a source for the theoretical part of this problem?
It should be on testing whether a rectangle can fit into some area, I guess...

Thanks in advance.