This page is still under construction.

Parts of this page are still being built. What you see may change.

Request for Permission

Time limit1sMemory limit128 MB

Summary
Given a convex country, M nearest-station Voronoi cells, and a straight flight segment outside the border, list the cells the flight crosses in order.
Level

Hard8 of 10

Topics
Geometry, Brute force, Implementation, Simulation
Solved
No attempts yet

Problem

A world superpower is preparing an air strike on the far side of the globe, and to carry it out it must send several airplanes across another continent. A small country named TidyLand lies along that route and has received a request for permission to fly through its airspace.

The border of TidyLand is a convex polygon. TidyLand's airspace is divided into segments, and each segment is monitored and controlled by exactly one air-control station. The segments are formed so that every point of the airspace is controlled by the station that is nearest to that point.

The request specifies the starting and ending coordinates of the flight (both lie outside TidyLand). The airplane flies in a straight line at a constant altitude; since all control stations share the same altitude, the whole problem is treated in the plane. TidyLand's Air Space Central wants to know which segments the airplane passes through, in the order it enters them.

Input

The first part of the input describes the border of TidyLand. The first line contains a single integer NN, the number of sides of the border polygon (3≤N≤203 \le N \le 20). Each of the next NN lines contains the integer coordinates XB,i,YB,iX_{B,i}, Y_{B,i} of a vertex (1≤XB,i,YB,i≤1001 \le X_{B,i}, Y_{B,i} \le 100, i=1…Ni = 1 \dots N). The vertices are listed in clockwise order.

The second part describes the air-control stations. First, a single line contains the integer MM, the number of stations (1≤M≤201 \le M \le 20). Then the ii-th of the next MM lines contains the integer coordinates XC,i,YC,iX_{C,i}, Y_{C,i} of the ii-th station. All stations share the same altitude.

The last part describes the flight path. One line contains four integers X1,Y1,X2,Y2X_1, Y_1, X_2, Y_2 (each between 00 and 100100), where (X1,Y1)(X_1, Y_1) is the start and (X2,Y2)(X_2, Y_2) is the end. Both points lie outside TidyLand.

Output

Print two lines. The first line contains the number of segments the airplane passes through. The second line lists the numbers of those segments, separated by single spaces, in the order the airplane enters them. The stations (segments) are numbered from 11 to MM in the order they are given in the input.

If the airplane does not enter TidyLand's airspace at all, print a single line containing 00.

Examples3

  1. Example 1

    Input
    5
2 1
3 4
6 5
7 3
5 1
3
5 2
4 3
6 3
3 0 8 4
    Expected output
    2
1 3

  2. Example 2

    Input
    4
1 1
1 10
10 10
10 1
2
3 5
7 5
0 5 11 5
    Expected output
    2
1 2

  3. Example 3

    Input
    4
1 1
1 10
10 10
10 1
3
2 5
5 5
8 5
0 5 11 5
    Expected output
    3
1 2 3