Our colleagues from the Department of Civil Engineering are working in a large suburban condominium, with hundreds of houses, each one with a backyard. Since they are concerned with environmental issues, they want to provide new owners with practical and environment friendly solutions. One of those solutions is the installation of a clothes line in each backyard, as long as possible. For this task they need our help to find the maximum length of the clothes line to be stretched in each backyard. Fortunately each backyard can be seen as a simple convex polygon. Can you help them?
Given N backyards, each described by providing the coordinates for each vertex of a simple convex polygon, your task is to find the maximum length of a clothes line that can be stretched in each backyard.
The number N of backyards in the first line. Then each backyard is described by the coordinates of each corner, starting with the number K of corners in a single line followed by K lines with the coordinates (two integers Xi,Yi separated by a single space) in counterclockwise order.
For each backyard you should output the ids i and j of the two vertices in the polygon that are at the maximum distance, where 0 ≤ i < j < k are the identifiers of each coordinate following the input order. If there is more than one pair of points at the maximum distance, you should output the lowest pair sorting first by i and, for the same i, sorting by j.
| 1 | ≤ N | ≤ 5 | Number of backyards |
| 3 | ≤ K | ≤ 100,000 | Number of corners in one backyard |
| −230 | ≤ Xi, Yi | ≤ 230−1 | Coordinates of points |
2 3 0 0 4 0 0 3 4 0 1 5 0 10 1 5 2
1 2 0 2
This document was translated from LATEX by HEVEA.