minimario's blog

CEOI 2007 Sail
By minimario, history, 7 years ago, In English

Hi,

The task is something like this: given some files with N<=1000 triangles, piece them together to make a rectangle. (Tests are given beforehand, there's no TL).

I couldn't find the solution anywhere, and I'm shocked a task like this would have a solution at all. I can't even imagine any heuristics to use to solve this problem.

So does anyone have any ideas? :) For convenience, tests can be downloaded here

Thanks,

minimario

  • Vote: I like it
  • +26
  • Vote: I do not like it

»
7 years ago, # |
← Rev. 2   Vote: I like it -32 Vote: I do not like it
  1. club triangles based on slopes of the sides.
  2. try to fit the edges of the plank first, cz we know their dimensions.
  3. try to see if the valley formed between 2 triangles can be fitted with some other triangles. one way is to check slopes of the sides, and keep checking if some triangles can be fit inside to completely enclose the valley.

Why downvotes? I'm just trying to help. I know it's not correct, but still, no need for downvoting people who try to help.

→ Reply
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

The blog's disappeared from the recent actions feed, but I still haven't found anything toward a solution. Anything would be great :)

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Sorry to bump again, but I'm interested in any ideas for this as well.

    → Reply