0074. TV

Имя входного файла:	tv.in
Имя выходного файла:	tv.out
Ограничение по времени:	1 s
Ограничение по памяти:	64 megabytes

Recently the citizens of the planet Nevera has developed TV. To broadcast TV signal they have decided to build M large broadcasting towers in large cities and N small retranslating towers in smaller towns.

Each of the large towers has TV studio assigned to it that broadcasts its own program from this tower. Each tower (no matter, large or small) also has a retranslator that receives all available programs and rebroadcasts them. All receivers and transmitters are attached to the tops of the corresponding towers.

Given coorindates and heights of all towers, you have to find for each tower which programs it can receive.

You should assume that radio waves propagate only in the area of direct visibility (along lines segments that do not intersect but may touch the surface of the planet). Assume that the speed of the transmission is infinite and that there is no intensity fading.

Input file

The first line of the input file contains three integer numbers M, N (1 ≤ M, N ≤ 100) and R – planet radius in kilometers (1000 ≤ R ≤ 15000). Next M+N lines contain descriptions of TV towers. First M of them describe large towers, next N – small ones.

Each description consists of nine components: latitude: degrees, minutes, seconds, hemisphere; longitude: degrees, minutes, second, hemisphere; tower height.

Degrees are integer numbers ranging from 0 to 90 for latitude and from 0 to 180 for longitude. Minutes and seconds are integer numbers from 0 to 59. Northern hemisphere is specified using character N, southern – S, eastern – E, and western – W. If the point belongs to both hemispheres it can be specified using any one. Tower height is specified in meters and is ranging from 0 to 1,000,000,000).

All towers are situated in different points of the planet.

All numbers and charactes in one line are separated by one or more spaces.

Output file

Output file must contain M+N lines, corresponding to different towers in the order they are given in the input file. For each tower you must output the list of all programs that can be received on this tower in increasing order, terminated by zero. Programs are identified by the number of the tower that the TV studio creating this program is assigned to. Numbers must be separated by spaces.

Examples:

tv.in	tv.out
3 4 6378 60 0 0 N 30 0 0 E 300 53 30 0 N 37 30 0 E 500 49 0 0 N 0 0 0 W 300 58 50 0 N 32 0 0 E 1000 57 20 0 N 33 0 0 E 1000 55 55 0 N 35 30 0 E 1000 54 30 0 N 36 30 0 E 600	1 2 0 1 2 0 3 0 1 2 0 1 2 0 1 2 0 1 2 0

Источник: Petrozavodsk Winter 2003. Our Special Contest on Geometry, Wednesday, February 05
Автор: Andrew Lopatin, Nick Durov

Обсудить       Отправить решение



Версия для печати