Closest Diagonal to Vertex 0 in a Triangulated Polygon

Given a convex polygon with n vertices numbered 0 to n-1 in clockwise order, a triangulation is formed by drawing n - 3 non-crossing diagonals (i.e. they may only intersect at vertices). Among these diagonals, your task is to find the one that is closest to vertex 0, where the distance is defined as the minimum Euclidean distance from vertex 0 to any point on the diagonal.

You are required to implement the function solve with the following signature:

int solve(int n)

This function may call the helper function query defined as:

int query(int x, int y)

Here, query(x, y) returns 1 if there is a diagonal directly connecting vertices x and y, and returns 0 otherwise.

If the correct answer diagonal is (a, b), your solve function should return the integer value a × n + b. In case there are multiple diagonals with the same (minimum) distance to vertex 0, output any one of them.

Note (Interactive Protocol): In an interactive setting, you do not know the endpoints of the diagonals in advance; you are allowed to use a limited number of queries via the query function. For the purpose of this problem, the input provides the polygon and its diagonals, and you may simulate queries accordingly.

Distance Calculation: Assume the polygon is regular and inscribed in a unit circle. The coordinate for vertex i is given by \( (\cos(\frac{2\pi i}{n}),\; \sin(\frac{2\pi i}{n})) \). For a diagonal connecting vertex i and vertex j, compute the distance from vertex 0 to the line segment joining these two vertices. Specifically, if the projection of vertex 0 onto the line through the two endpoints lies within the segment, use the perpendicular distance; otherwise, use the smaller of the distances from vertex 0 to the endpoints.

inputFormat

The input starts with an integer n (n ≥ 4) denoting the number of vertices of the polygon. It is followed by n - 3 lines, each containing two integers a and b (0 ≤ a, b ≤ n-1) representing a diagonal drawn in the triangulation.

outputFormat

Output a single integer, which is equal to a × n + b where (a, b) is the diagonal (with a query-confirmed existence) that is closest to vertex 0. If multiple diagonals are equally close, output any one of them.

sample

4
0 2

2