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.
- The path
- 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