Description

Given an $N$-gon whose vertices are labeled clockwise as $0 \sim N-1$, A has drawn $n-3$ diagonals. It is guaranteed that these $n-3$ diagonals have no extra intersections except at vertices.

Now A wants J to guess which diagonal has the smallest eJ distance to point $0$, and also report that distance.

J cannot know the answer by mind reading, so he can only ask A for some clues. A tells J the value of $n$, and agrees that J may ask whether there is a diagonal between a pair of vertices, but J has a limit on the number of queries.

J still wants to AK eJOI, so this problem is handed to you.

Interaction rules

You need to include the header file triangulation.h.

int solve(int n)

• This function can only be called once.
• $n$: the number of vertices of the polygon.
• Suppose the answer diagonal is $(a,b)$. This function should return $a \times n+b$.
• If multiple diagonals are closest to point $0$, you may return any one of them.

The solve function may call the following function multiple times:

int query(int x, int y)

• $x,y$: represent one query.
• $0 \le x,y \le n-1$.
• If $(x,y)$ exists, return $1$, otherwise return $0$.

7

Hint

Sample 1

The sample input format only contains one integer $n$.

Constraints

For $100\%$ of the testdata, $5 \le n \le 100$.

Assume $q$ is the number of queries you make for one test case. Let $w=\dfrac{n \times (n-3)}{2}$. Your score for one test case is:

• If the queries are invalid, the answer is wrong, or $w<q$, you will get $0\%$ of the score.
• If $n<q \le w$, you will get $10+60 \times \dfrac{w-q}{w-n}\%$ of the score.
• If $q \le n$, you will get $100\%$ of the score.

Thanks to

Notes

Translated from eJOI 2020 Day1 B Triangulation。

Translated by ChatGPT 5