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.
Submitting an official solution before solving the problem yourself is a bannable offence.
- Loop through all permutations of the points.
- C++ users can use
std::next_permutation
.
- C++ users can use
- (Optimize) Restrict w.l.o.g. to permutations that start with "".
- For each permutation, check that it forms a simple polygon. If not, discard it.
- The path is a left turn iff .
- We use this to write boolean .
- crosses iff and .
- To check for simplicity, test all pairs of non-adjacent edges.
- If simple, compute the area, , and the probability .
- 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 possible orderings of that heptagon.
Comments