Editorial for TLE '16 Contest 6 (Mock CCC) S2 - Paper Stapling
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
In case the reader has never folded over stapled paper, here is a paragraph describing the process. First, one takes two pieces of paper, align them so that the corners match. A staple punctures the 2 sheets of paper, and the region of paper near the staple is attached together. Now lift the first page and fold it under the other sheet. The first sheet should make a full revolution. However, part of the second page is missing.
When stapled paper is folded, the fold forms a triangle containing the staple. Suppose the triangle's coordinates are
In summary, the pair
The first approach is to realize that the optimal triangle can take one of three different forms.
- Form 1:
, . The optimal triangle disregards the staple's second endpoint. This form is invalid when the second staple is outside the triangle fold. - Form 2:
, . This is similar to form 1. Note that only this form needs to be considered to get subtask 2. This form can also be invalid. - Form 3:
, is defined by the line formed by the staple. This form is invalid if the slope is positive, 0, or infinite/undefined. Otherwise, this form is valid.
The answer is the valid form with the least amount of area.
Time complexity:
The second approach is to perform a binary/ternary search. The lowest possible slope is a large negative number, and the highest possible slope is a small negative number. The slopes
Time complexity:
Comments