4003 - CK

Created by V Copa UPR - Elio Alejandro Govea Aguilar
Added by eliogovea (2018-05-23)
Limits
Total Time: 36000 MS | Test Time: 1500 MS |Memory: 512 MB | Output: 64 MB | Size: 16 KB
Enabled languages
Available in

Description

Ana María received a cake for her birthday, a very special one. Looking at it from above is a convex polygon of n (3 <= n <= 400000) sides, and its height is constant. After everyone congratulated her, Ana Maria will cut the cake, but with a cut that divides it into two parts with equal volume, go through two of its vertices and be perpendicular to the table where it is placed. Unfortunately that is not always possible and will be satisfied with passing through one of the vertices, but only after knowing how to execute the cut. For this she needs to know for certain vertices how the cut will be.
Ana María recibió ayer por su cumpleaños un cake, uno muy especial. Mirándolo desde arriba es un polígono convexo de n (3 <= n <= 400000)  lados, y su altura es constante. Despues que todos la felicitaron Ana María va a cortar el cake, pero con un corte que lo divida en dos partes con igual volumen, pase por dos de sus vértices y sea perpendicular a la mesa donde esta puesto. Lamentablemente eso no es siempre posible y se conformará con que pase por uno de los vértices, pero solo después de saber como ejecutará el corte. Para ello necesita saber para determinados vértices como será el corte.
;jsessionid=28AF4703850983778699FE1B5D14EA39
Ana María received a cake for her birthday, a very special one. Looking at it from above is a convex polygon of n (3 <= n <= 400000) sides, and its height is constant. After everyone congratulated her, Ana Maria will cut the cake, but with a cut that divides it into two parts with equal volume, go through two of its vertices and be perpendicular to the table where it is placed. Unfortunately that is not always possible and will be satisfied with passing through one of the vertices, but only after knowing how to execute the cut. For this she needs to know for certain vertices how the cut will be.

Input specification

A line with a number that n (3 <= n <= 400000) represents the number of sides of the polygon that represents the surface of the cake. They follow n lines each one with two integers x,y the vertices of the polygon. It is guaranteed that the polygon can be placed in a square with sides parallel to the coordinate axes and side less than or equal to 100000. The next line contains a number q representing the number of questions. They follow lines each with a number v (0 <= v <n), the vertex from which you want to make the cut.
Una línea con un número que n (3 <= n <= 400000) representa la cantidad de lados del polígono que representa la superficie del cake. Siguen n  líneas cada una con dos enteros x, y los vértices del polígono. Se garantiza que el polígono se puede poner en un cuadrado con lados paralelos a los ejes de coordenadas y lado menor o igual que 100000. La siguiente línea contiene un número q  que representa la cantidad de preguntas. Siguen líneas cada una con un número v (0 <= v < n), el vértice desde el que se quiere hacer el corte.
;jsessionid=28AF4703850983778699FE1B5D14EA39
A line with a number that n (3 <= n <= 400000) represents the number of sides of the polygon that represents the surface of the cake. They follow n lines each one with two integers x,y the vertices of the polygon. It is guaranteed that the polygon can be placed in a square with sides parallel to the coordinate axes and side less than or equal to 100000. The next line contains a number q representing the number of questions. They follow lines each with a number v (0 <= v <n), the vertex from which you want to make the cut.

Output specification

q lines with the answers to each question. Each answer must be a pair of integers x,y it represents the first point with integer coordinates which the ray pass through, which begins with the vertex of the question and cuts the polygon into two parts with the same area.
q líneas con las respuestas a cada pregunta. Cada respuesta debe ser un par de enteros x, y  que representa el primer punto con coordenadas enteras por el que pasa el rayo que comienza con el vertice de la pregunta y corta el polígono en dos partes con igual area iguales.
;jsessionid=28AF4703850983778699FE1B5D14EA39
A line with a number that n (3 <= n <= 400000) represents the number of sides of the polygon that represents the surface of the cake. They follow n lines each one with two integers x,y the vertices of the polygon. It is guaranteed that the polygon can be placed in a square with sides parallel to the coordinate axes and side less than or equal to 100000. The next line contains a number q representing the number of questions. They follow lines each with a number v (0 <= v <n), the vertex from which you want to make the cut.

Sample input

3
0 0
1 0
0 1
1
0

Sample output

1 1

Hint(s)

If the starting point of the cut is (0,0) and the cut must be along the x axis in the direction of positive x, then the answer would be (1,0) which is the first point with integer coordinates that the ray passes through after the initial point.

Input example
4
0 0
1 -1
2 0
1 1
1
0

Output example
1 0
Entiendase rayo como semirrecta.
Si el punto inicial del corte es (0, 0) y el corte debe ser por el eje x en el sentido de las x positivas, entonces la respuesta sería (1, 0) que es el primer punto con coordenadas enteras por el que pasa la semirecta después del inicial.

Ejemplo entrada
4
0 0
1 -1
2 0
1 1
1
0

Ejemplo salida
1 0;jsessionid=28AF4703850983778699FE1B5D14EA39
If the starting point of the cut is (0,0) and the cut must be along the x axis in the direction of positive x, then the answer would be (1,0) which is the first point with integer coordinates that the ray passes through after the initial point.

Input example
4
0 0
1 -1
2 0
1 1
1
0

Output example
1 0