Editorial for TLE '16 Contest 6 (Mock CCC) S2 - Paper Stapling - Olympiads Online Judge

Editorial for TLE '16 Contest 6 (Mock CCC) S2 - Paper Stapling

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.

Author: d

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 $(0,0)$ $(0, 0)$ , $(u,0)$ $(u, 0)$ , and $(0,v)$ $(0, v)$ . This triangle is possible if and only if the staple is located inside the triangle. Also, if the staple touches the perimeter, it is still considered to be inside.

In summary, the pair $u$ $u$ , $v$ $v$ is valid if the staple's endpoints are in the triangle fold with coordinates $(0,0)$ $(0, 0)$ , $(u,0)$ $(u, 0)$ , and $(0,v)$ $(0, v)$ . From here, there are two approaches to solve the problem.

The first approach is to realize that the optimal triangle can take one of three different forms.

Form 1: $u = 2x_1$ $u = 2 x_{1}$ , $v = 2y_1$ $v = 2 y_{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: $u = 2x_2$ $u = 2 x_{2}$ , $v = 2y_2$ $v = 2 y_{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: $u$ $u$ , $v$ $v$ 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: $\mathcal{O}(1)$ $O (1)$

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 $-10^9$ $- 10^{9}$ and $-10^{-9}$ $- 10^{- 9}$ are sufficient to pass this problem. It is easy to get the minimal area triangle that has a specified slope.

Time complexity: $\mathcal{O}(x)$ $O (x)$ where $x$ $x$ is the number of reductions performed by the binary search. This is a relatively small constant.

Comments

There are no comments at the moment.