Имя: Пароль: Зарегистрироваться Восстановить пароль
10/12/2023 03:32:11

# Рабочее место участника

## Задачи

984. Hosting

Ограничения: время – 1s/2s, память – 16MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)

There are n major cities in the world. These cities are labeled from 0 to n-1, which in order to form a convex polygon on a single plain. Each year, the ACM-ICPC Committee has to select one city from these cities to host the ACM-ICPC world final. The selection process is described as follows:
• At the first phase, they create a shortlist. In order to do so, with a starting city s and a selection step d, they put all the cities with label s+i*d into the shortlist for all i such that 0\ ≤\ i and s+i*d\ <\ n.
• At the second phase, one city will be selected from the shortlist to organize the ACM-ICPC world final. At that year, they might choose the city which is the most to the North (maximal y coordinate), to the South (minimal y coordinate), to the East (maximal x coordinate) or to the West (minimal x coordinate).
There is a cost associated with each city to organize the ACM-ICPC world final. It is assumed that this cost does not change over years. Your task is to compute the total cost the ACM-ICPC Committee has to pay to organize the ACM-ICPC world finals for a given number of years.
Input
The first line contains the integer number n (1\ ≤\ n\ ≤\ 100\ 000). Each line of the next n lines describes one city, which contains three integer numbers x, y, and c. The pair (x,\ y) is a 2-D coordinate specifying the location of the city (-200\ 000\ ≤\ x,\ y\ ≤\ 200\ 000). c is the associated cost to organize the ACM-ICPC world final in that city (1\ ≤\ c\ ≤\ 1000). The next line contains an integer number m, which is the number of years the ACM-ICPC Committee want to compute the cost to organize the ACM-ICPC world finals (1\ ≤\ m\ ≤\ 100\ 000). Each line of the next m lines contains three integer numbers s, d (0\ ≤\ s\ <\ n; 1\ ≤\ d), and p. The value of p can be 0, 1, 2 or 3 for selecting the city most to North, the South, the East or the West respectively.
Output
Write the total cost for the ACM-ICPC Committee to organize the ACM-ICPC world finals.

Sample Input 1

4
-1 1 2
0 4 3
5 3 2
1 -1 2
2
0 1 0
0 2 1

Sample Output 1

5

Sample Input 2

3
0 0 2
1 1 3
2 10 2
2
1 1 1
0 2 0

Sample Output 2

5
Источник: РГУ им. И.Канта, осенний командный турнир, 2007