Background

Instructions for use.

In this problem, $(A,B)$ represents a diagonal from $A$ to $B$.

Define the eJ distance from vertex $A$ to vertex $B$ in a regular polygon as the maximum of: the number of edges when going from $A$ to $B$ clockwise, and the number of edges when going from $A$ to $B$ counterclockwise. Based on this definition, we can also define the eJ distance from a vertex $A$ to a diagonal $B$ of the polygon: it is the maximum of the number of edges from $A$ to one endpoint of diagonal $B$ (the closer endpoint) when going clockwise, and the number of edges when going counterclockwise.

For example, the eJ distance from point $0$ to diagonal $(0,5)$ is $5$. Going clockwise needs $5$ edges, going counterclockwise needs $2$ edges, so the answer is $\max\{5,2\}=5$.

Problem 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