6728번 - Request for permission 다국어

The World’s superpower is preparing for an air attack in another part of the globe. For that reason they need to send some airplanes over the continent. Among others, a little country TidyLand received a request for a permission to fly through their air space.

The borders of TidyLand have a shape of a convex polygon. The air space of TidyLand is divided into segments. Each segment is monitored and controlled by one air control station. The segments are designed in such a way that each point of the TidyLand’s air space is controlled by the control station, which is the nearest to that point.

The request for a permission specifies the starting and ending coordinates for the flight (both of them are outside of TidyLand). The planes will fly along a straight horizontal line. TidyLand Air Space Central needs to know which segments will be crossed or touched by the planes of the foreign army.

First part of the input specifies the borders of TidyLand. First line contains a single integer N, the number of sides that form the TidyLand borders polygon. (3 ≤ N ≤ 20). The following N lines contain integer coordinates X_B[i], Y_B[i] (i = 1..N) of the verteces of the polygon. (1 ≤ X_B[i],Y_B[i] ≤ 100). The verteces are enumerated systematically in a clockwise direction. The second part of the input specifies the locations of the air control stations. First, a single integer M, the number of control stations, is given at a separate line, (1 ≤ M ≤ 20). It is followed by M lines with integer coordinates X_C[i],Y_C[i] (i = 1..M) of the air control stations: i-th line contains the coordinates of the i-th control station. You can assume that all control stations have the same altitude. Last part describes the line of flight. It consists of a single line with 4 integers X₁ , Y₁ , X₂ , Y₂ (all are between 0 and 100), where [X₁,Y₁] are starting coordinates, and [X₂,Y₂] are ending coordinates. Both points lie outside of TidyLand.

The output will consist of two lines. The first line will contain the number of segments, which will be crossed by the planes. The second line will list the numbers of segments through which the planes will cross in the same order as they will be entered by the planes. If the plane will not enter the air space of TidyLand, the output should consist of a single line containing 0.