Подразделы

Другие разделы

Дата и время

24/11/2024 12:16:10

Авторизация

Лето 6

A. Метрополитен B. Очень легкая задача C. Шахматная доска D. Интересный треугольник E. Galaxy F. Robot G. Schedule H. Ancestor I. Grid J. Hosting K. BitSort

J. Hosting

Ограничения: время – 1s/2s, память – 16MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение 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

Sample Output 1

Sample Input 2

Sample Output 2

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