yermak0v's blog

Procon 2013
By yermak0v, 11 years ago, translation, In English

Just now ends Procon 2013 on Codechef http://www.codechef.com/PRCN2013/
I propose to discuss here problem solving. How solve 1-st?

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

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Just backtrack all possible permutations recursively (remembering rooms for each person at the same time). At the end, check all the rules. Print the first good result.

How to solve PC04? I think, that the hardest part was to match if the given figure is QUADRILATERAL or NONE. How to do that easily?

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 8   Vote: I like it 0 Vote: I do not like it

    you should check 3 things:

    1. Any 3 points is on 1 line

    2. Any two points coincides

    3. Any two not adjacent side of QUADRILATERAL intersects (I don't mean their continuation) , AB intersects CD or BC intersects AD

    If any from this 3 happens its not QUADRILATERAL else it is

    → Reply