1901:Hypertransmission

Special Judge 特殊评判
题目描述
The president of the Galactic Federation has recently decided that all planets of the galaxy must establish hyper-radio centers to broadcast their programs. To ensure the process, the government has signed the contract with well known hyper-radio equipment manufacturer Trojan Horse Ltd. By the terms of this contract the company has to provide N hypertransmitters, one for each planet of the Federation.

It is known that there are two main political movements in the galaxy: industrialism and ecologism. On each planet of the galaxy one of these movements has the majority. It is clear that after establishing the hyper-radio station on the planet, the political programs of the station will support the movement that has the majority on this planet.

All transmitters supplied by Trojan Horse Ltd will have the same range, so hyper-radio programs from each planet will be heard at the distance not exceeding R parsecs from it. Since the company director is actually the agent of the Dark Empire, he wants to choose R in such a way, that it would destabilize the political situation in the Galactic Federation.

More precisely, for each planet A let N+(A) be the number of planets where the same political movement as in A has the majority and hyper-radio programs from A are received, including A itself. Similarly, let N-(A) be the number of planets where the other political movement has the majority and hyper-radio programs from A are received. The planet A is called destabilizing if N+(A) < N-(A).

Your task is to choose such R that the number D of destabilizing planets is maximal possible. Since increasing transmitter's range requires more resources for its manufacturing, you must find the smallest possible R maximizing D.
输入解释
The first line of input contains N -- the number of planets in the Galactic Federation (1 <= N <= 1000). Next N lines contain four integer numbers xi, yi, zi, and pi each and describe the planets: xi, yi, and zi specify the coordinates of the planet in space, pi = 0 if the industrialists have the majority on the planet and pi = 1 if the ecologists have the majority. All coordinates do not exceed 10 000 by their absolute value. No two planets occupy the same point.
输出解释
First output D -- the maximal possible number of destabilizing planets, and then followed on the second line by a non-negative real number R -- the minimal range that hyper-radio transmitters must have so that the number of destabilizing planets is D. R must be accurate within 10-4 of the correct answer.
输入样例
4
0 0 0 1
0 1 0 0
1 0 0 0
1 1 0 1
输出样例
4
1.0000

该题目是Virtual Judge题目,来自 北京大学POJ

源链接: POJ-1901

最后修改于 2020-10-29 06:17:12 UTC 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
10000 30000

·

·

·

·

登陆或注册以提交代码