Hypertransmission
Time limit1sMemory limit128 MB
Given N points in 3D each labeled 0 or 1, choose a squared radius R^2 to maximize the number of points where opposite-label neighbors outnumber same-label ones, then report that maximum and the smallest R^2 achieving it.
- Level
Hard8 of 10
- Topics
- Sorting, Prefix sum, Geometry, Brute force
- Solved
- No attempts yet
Problem
There are planets in a galactic federation. On every planet exactly one of two political movements --- industrialism or ecologism --- holds the majority. Each planet is equipped with an identical hyper-radio transmitter of range : a planet's broadcast is received by every planet lying within Euclidean distance of it, and every planet always receives its own broadcast.
For a planet , let be the number of planets that receive 's broadcast and share 's majority movement (this count includes itself), and let be the number of planets that receive 's broadcast but hold the opposite movement. Planet is called destabilizing when .
Choose the range so that the number of destabilizing planets is as large as possible. Among all ranges that attain this maximum , the range must be the smallest one.
Input
The first line contains the integer --- the number of planets (). Each of the next lines contains four integers , , , and describing one planet: are its coordinates in space and is its majority movement, with for industrialists and for ecologists. Every coordinate satisfies . No two planets occupy the same point.
Output
On the first line output --- the maximum possible number of destabilizing planets. On the second line output --- the square of the smallest range that achieves destabilizing planets. Because all coordinates are integers, the optimal range is either or the distance between two planets, so is always a non-negative integer; recover the range itself as .