Блог пользователя minimario

CEOI 2007 Sail
Автор minimario, история, 7 лет назад, По-английски

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

  • Проголосовать: нравится
  • +26
  • Проголосовать: не нравится

»
7 лет назад, # |
← Rev. 2   Проголосовать: нравится -32 Проголосовать: не нравится
  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.

→ Ответить
»
7 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

→ Ответить