Editorial for ICPC NAQ 2016 L - Unusual Darts


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
  • Loop through all permutations of the 7 points.
    • C++ users can use std::next_permutation.
  • (Optimize) Restrict w.l.o.g. to permutations that start with "1".
  • For each permutation, check that it forms a simple polygon. If not, discard it.
    • The path (a_x, a_y) \to (b_x, b_y) \to (c_x, c_y) is a left turn iff (b_x-a_x)(c_y-a_y)-(b_y-a_y)(c_x-a_x) > 0.
    • We use this to write boolean left(P, Q, R).
    • \overline{AB} crosses \overline{CD} iff left(A, B, C) \ne left(A, B, D) and left(C, D, A) \ne left(C, D, B).
    • To check for simplicity, test all 14 pairs of non-adjacent edges.
  • If simple, compute the area, K, and the probability p = \left(\frac{K}{2^2}\right)^3.
  • If generating permutations in lexicographic order, print the first one that works. Otherwise, select the lexicographically least one from among the 14 possible orderings of that heptagon.

Comments

There are no comments at the moment.