URI Online Judge | 1834


Por Edson Alves, Faculdade UnB Gama BR Brazil

Timelimit: 3

According to the Douglas Adams's "Hitchhiker's Guide to the Galaxy", the vogons are an alien race that inhabits the Vogosphere. In the author words:

"Here is what to do if you want to get a lift from a Vogon: forget it. They are one of the most unpleasant races in the Galaxy. Not actually evil, but bad-tempered, bureaucratic, officious and callous. They wouldn't even lift a finger to save their own grandmothers from the Ravenous Bugblatter Beast of Traal without orders - signed in triplicate, sent in, sent back, queried, lost, found, subjected to public inquiry, lost again, and finally buried in soft peat for three months and recycled as firelighters. The best way to get a drink out of a Vogon is to stick your finger down his throat, and the best way to irritate him is to feed his grandmother to the Ravenous Bugblatter Beast of Traal. On no account should you allow a Vogon to read poetry at you."

In the book, the vogons were responsible for Earth's destruction. The cause was simple: the planet was in the route of the new intergalactic autobahn. This is the typical vogon's way of life: too many races and several planets were destroyed to ease the intergalactic traffic.

Given two reference points that the new road must cross in a straight line and the coordinates and population of each planet in the spacial sector, write a program that generates a building report for the vogons.


The first line of the input contains the coordinates X1, Y1, X2, Y2 (-10.000 ≤ Xi, Yi ≤ 10.000) of the two reference points P1 and P2, separated by a single space. The coordinates are integers and the distance unit is the light-year.

The second line contains the number N (1 ≤ N ≤ 1.000) of the planets that belong to the spatial sector that the road crosses. The next N lines consist in the coordinates X and Y (-10.000 ≤ X, Y ≤ 10.000) and the number (in billions) of inhabitants H (1 ≤ H ≤ 100.000) of each planet. These values are integers separated by a single space.


The printed report has several lines. The first line contains the message "Relatorio Vogon #35987-2". The follow line must be the message "Distancia entre referencias: d anos-luz", where d is the distance between the two reference points, in light-years, with two decimal places.

In the next line must be printed the message "Setor Oeste:" and, in the next two lines, the messages "P planeta(s)" and "H bilhao(oes) de habitante(s)", where P is the number of the planets located in the left from the road (when traveled from first to second reference point) and H is the total of inhabitants from these planets. In the same way, must be printed three similar messages in reference to the "Setor Leste", the right side of the road.

Finally, must be printed, in the last line, the message "Casualidades: P planeta(s)", where P is the number of planets that were in the road line and, naturally, have to be destroyed by the vogons.

Input Samples Output Samples

-10 -10 30 30


1 10 6

5 5 8

2 0 4

-3 -3 30

-2 5 3

Relatorio Vogon #35987-2

Distancia entre referencias: 56.57 anos-luz

Setor Oeste:

- 2 planeta(s)

- 9 bilhao(oes) de habitante(s)

Setor Leste:

- 1 planeta(s)

- 4 bilhao(oes) de habitante(s)

Casualidades: 2 planeta(s)