Задача A. Пара ближайших точек

Входной файл: input.txt   Ограничение времени:4 сек
Выходной файл: output.txt   Ограничение памяти:16 Мб


На плоскости заданы N точек. Найти квадрат расстояния между ближайшими из них.

Формат входного файла

Входной файла содержит число N, за которым следует N пар чисел x y — координаты точек.

Формат выходного файла

В выходной файл требуется вывести одно число: квадрат расстояния между ближайшими точками.


2 ≤ N ≤ 100000. Все координаты — целые числа, не превышающие по модулю 16000.

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1 1
5 2
2 3

Problem B. Ganking

Author:A. Klenin
Input file: input.txt   Time limit:1 sec
Output file: output.txt   Memory limit:256 Mb


Popular on-line game "Attack Of The Moderns 3" is played by two teams of 5 players each. During the match, players run around the map and try to kill members of opposing team by attacking them with various weapons and magic spells. Killed players respawn after a certain period of time.

Players of the first team are numbered from 1 to 5, players of the second team are numbered from 6 to 10. All attacks are recorded by the game for statistics gathering. Each attack is described by values t, a, v, k, where t is a time in seconds since the game start, a — the number of the attacking player, v — the number of the player being attacked, k = 1 if this attack killed the victim and 0 otherwise.

Gank is an event when one or more players attack and kill a single opponent while his teammates are elsewhere and unable to help. Specifically: let G be a set of players who attacked the victim during the last T seconds of the game before the kill. A kill is counted as a gank, if in that period of time:

All the players from the set G who attacked the victim of the gank are considered the participants of this gank.

Your program must, given the value of T and a sequence of N attack descriptions, count the number of ganks each player has participated in.

Input file format

Input file contains integers N T followed by N quartets of integers ti ai vi k.

Output file format

Output file must contain 10 integers — the numbers of ganks for each player.


1 ≤ N ≤ 10000, 1 ≤ ti ≤ ti+1 ≤ 105, 1 ≤ T ≤ 105. Either 1 ≤ ai ≤ 5 < vi ≤ 10 or 1 ≤ vi ≤ 5 < ai ≤ 10. Time between sequential kills of the same victim is greater than T.

Sample tests

No. Input file (input.txt) Output file (output.txt)
7 4
1 1 6 0
2 2 6 0
5 3 6 1
10 7 1 1
10 7 2 1
20 8 1 1
20 3 7 1
0 1 2 0 0 0 0 1 0 0 

Problem C. Far Eastern Federal Clock

Author:A. Klenin
Input file: input.txt   Time limit:1 sec
Output file: output.txt   Memory limit:256 Mb


Once upon a time there was a large country with many provinces and a great government. The government noticed that citizens of the furthest province are unhappy, and decided to do something for them.

After a serious sociological research, the government decided that the main problem of the province is the fact that every citizen has to buy his own watch to measure time. Thus the government decided to build a large tower with a giant analog clock on it, so that citizens could look at the common clock and save money on watches.

Many efforts and resources were spent, and finally the clock has been built and officially started in a grand ceremony. As the ceremony finished, people noticed that the clock has a small problem — it measures time incorrectly.

Since all the money allocated to this project was already spent, it was impossible to fix the clock. Instead, the government introduced a new position of Senior Clock Manager, whose responsibility was to adjust the clock by manually moving its hands.

It was decreed that:

Since the clock hands are very heavy, the Clock Manager's job is not an easy one. To help him, find the period of adjustment minimizing the total distance by which he must move the clock hands throughout the day. The clock has two hands — for minutes and hours. Every minute, the minute hand jumps clockwise by t degrees, and the hour hand jumps by t / 12 degrees. (A correct clock should have t = 6).

An adjustment is made immediately after the jump, and the effort is equal to the sum of angles between the current and the correct positions of both minute and hour hands.

In the first sample, the clock moves twice as fast as it should, so every minute the error is increased by one minute. This requires an adjustment every two minutes.

In the second sample, the clock moves three times as fast as it should, but the acceptable error is much higher. It turns out that every 30 minutes the position of the minute hand coincides with the correct one, so if we choose the interval of 30 minutes, only the hour hand must be moved.

Input file format

Input file contains floating point number t followed by integer m.

Output file format

Output file must contain the minimum total effort s in degrees, with an absolute error less than 102, and the corresponding adjustment period p, 1 ≤ p ≤ 24 * 60. If there are several answers with the same total effort, output the one with the maximum p.


0 ≤ t ≤ 104, 1 ≤ m ≤ 104, t has no more than 3 digits after decimal point.

Sample tests

No. Input file (input.txt) Output file (output.txt)
12 1
9360.0000 2
18.0 90
1440.0000 30
6 1
0.0000 1440

0.044s 0.006s 11