After about five decades, people have started showing interest in the Bermuda Polygon again. Rumors say, there are some points on the earth’s surface which can cause ships and aircrafts to disappear within its enclosed region under unknown circumstances. The points where the ships disappear are known as ”ship-sinks’, and the points causing this phenomena are ”bermuda-points’. Geometers and Maritime scientists from all around the globe have gathered to investigate the existence of any such thing. Little Anita, being a talented programmer and crazy about geometry is invited to be the part of this team. Bermuda Polygon was previously known as following:
”It is a Spherical Polygon formed by connecting some coordinates (bermuda-points) on the surface of earth such that the enclosed region contains one or more ship-sinks.” The team of scientists clarified a bit more on the matter: • Bermuda Polygon (if exists) can only be found in the half sphere formed by all the points with latitude within range (-90, +90) and longitude within range (0, +180), i.e. −90 < Latitude < 90 and 0 < Longitude < 180. • Every Spherical Polygon on the earth’s surface can divide the earth in two bounded parts with non zero surface area. But Bermuda Polygon will surely be the one with the smaller surface area. From definition, a Spherical Polygon of K(> 2) points (each defined as Pi) on the earth’s surface is the set of following ordered geodesic line segments: P1P2,P2P3,...,PkP1 Where, no two segments intersect with each other. The geodesic line segment between two points on a sphere is the shortest connecting curve lying entirely on the surface of the sphere.
2/2 The team has analyzed satellite footages for last couple of years. These footages are related to ships on international water. They have found some interesting leads and pinpointed some sets of coordinates which seem to be very mysterious based on recent events. Now, they have given Anita the job to shortlist those sets where the Bermuda Polygon probably exists. As you were her ”Geo’ learning partner, she asks you for help. Anita told you that, a given set of coordinates (points with latitude and longitude value) can probably indicate the existence of the Bermuda Polygon if you can draw a Spherical Polygon by taking minimum number of points from the given set such that all other points of the set are within the region enclosed by its contour (including its boundary). Here, the other points are the points of ship-sinks. Anita can’t be sure about a probable Bermuda Polygon if there are no ship-sinks. You will be given latitude and longitude of N points. Points will be located on one half of the earth’s sphere (as clarified by the team of scientists). Radius of that sphere is 103. You have to find whether these points indicate the existence of the Bermuda Polygon. Input The first line will contain a single integer D (D ≤ 150), denoting the number of data sets. The first line of each data set will contain N (3 ≤ N ≤ 200). Next N lines will contain two integers denoting Latitude and Longitude of a point respectively. Latitude is given as an angular measurement ranging from − 90° (South Pole) to +90° (North Pole). Longitude is given as an angular measurement ranging from 0° at the Prime Meridian to +180° eastward. The ranges are exclusive and the coordinates are unique. That means, −90 < Latitud < 90 and 0 < Longitude < 180. Output If there exists a probable Bermuda Polygon, print the id of the bermuda-points (the order they appear in the input, from 0 to N − 1) in ascending order separated by spaces. If the existence of the Bermuda Polygon is inconclusive, then print ‘inconclusive’ without quotes. Sample Input 2 5 40 150 30 10 -10 120 -20 20 30 30 4 0 10 0 15 0 20 0 25 Sample Output 0123 inconclusive