21/11/2024 20:39:17

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

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

727. Walk

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

Alice would like to visit Bob. However, they live in a hilly landscape, and Alice doesn't like to walk in hills. She has a map of the area, showing the height curves. You have to calculate the total altitude climbed, and the total altitude descended, for the route which minimizes these numbers. It does not matter how far she has to walk to achieve this.

Since you don't know what the landscape looks like in between the height curves, you cannot know exactly how much climb and descent she will actually get in practice, but you should calculate the minimum possible under optimal conditions based on what you can deduce from the map.

The map is represented as an `"xy"` grid. Alice lives in (0, 0), and Bob lives in (100000, 0). The height curves are represented as polygons, where a polygon cannot intersect itself or another polygon. Furthermore, neither Alice nor Bob lives exactly on a height curve.

Second test case from sample input (compressed).

Input

On the first line one positive number: the number of testcases, at most 100. After that per testcase:

One line with `0\ ≤\ N\ ≤\ 2500`, the number of height curves.
One line for each height curve, with `1\ ≤\ H_i\ ≤\ 1000` being the height of the curve, `3\ ≤\ P_i\ ≤\ 2000` the number of vertices in the polygon, and the vertices `x_1,\ y_1,\ …,\ x_{P_i},\ y_{P_i}` having integral values `-300\ 000\ ≤\ x_i,\ y_i\ ≤\ 300\ 000`.

There will be no more than 200000 polygon vertices in total in all test cases.

Output

Per testcase:

One line with two numbers; the total altitude climbed and the total altitude descended.

Sample Input

2
2
20 3 10 10 0 -10 -10 10
25 3 20 20 0 -20 -20 20
3
100 4 -1 1 1 1 1 -1 -1 -1
300 8 -2 2 2 2 2 -2 5 -2 5 1 6 1 6 -3 -2 -3
50 8 3 3 100001 3 100001 -1 7 -1 7 2 4 2 4 -1 3 -1

Sample Output

5 0
200 250

15/12/2007	Тренировка (задачи ACM ICPC NWERC 2007) (J)
04/07/2011	Лето 2011 - дорешивание (12J)