Editorial for ICPC NAQ 2016 L - Unusual Darts - Olympiads Online Judge

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$ ~7~ points.
- C++ users can use std::next_permutation.
(Optimize) Restrict w.l.o.g. to permutations that start with " $1$ ~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)$ ~left(P, Q, R)~.
- $\overline{AB}$ ~\overline{AB}~ crosses $\overline{CD}$ ~\overline{CD}~ iff $left(A, B, C) \ne left(A, B, D)$ ~left(A, B, C) \ne left(A, B, D)~ and $left(C, D, A) \ne left(C, D, B)$ ~left(C, D, A) \ne left(C, D, B)~.
- To check for simplicity, test all $14$ ~14~ pairs of non-adjacent edges.
If simple, compute the area, $K$ ~K~, and the probability $p = \left(\frac{K}{2^2}\right)^3$ ~p = \left(\frac{K}{2^2}\right)^3~.
- Use the shoelace formula to compute area.
If generating permutations in lexicographic order, print the first one that works. Otherwise, select the lexicographically least one from among the $14$ ~14~ possible orderings of that heptagon.

Comments

There are no comments at the moment.