This page is still under construction.

Parts of this page are still being built. What you see may change.

Hypertransmission

Time limit1sMemory limit128 MB

Summary
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 NN 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 RR: a planet's broadcast is received by every planet lying within Euclidean distance RR of it, and every planet always receives its own broadcast.

For a planet AA, let N+(A)N^+(A) be the number of planets that receive AA's broadcast and share AA's majority movement (this count includes AA itself), and let N−(A)N^-(A) be the number of planets that receive AA's broadcast but hold the opposite movement. Planet AA is called destabilizing when N+(A)<N−(A)N^+(A) < N^-(A).

Choose the range RR so that the number DD of destabilizing planets is as large as possible. Among all ranges that attain this maximum DD, the range must be the smallest one.

Input

The first line contains the integer NN --- the number of planets (1≤N≤10001 \le N \le 1000). Each of the next NN lines contains four integers xix_i, yiy_i, ziz_i, and pip_i describing one planet: (xi,yi,zi)(x_i, y_i, z_i) are its coordinates in space and pip_i is its majority movement, with pi=0p_i = 0 for industrialists and pi=1p_i = 1 for ecologists. Every coordinate satisfies ∣xi∣,∣yi∣,∣zi∣≤104|x_i|, |y_i|, |z_i| \le 10^4. No two planets occupy the same point.

Output

On the first line output DD --- the maximum possible number of destabilizing planets. On the second line output R2R^2 --- the square of the smallest range that achieves DD destabilizing planets. Because all coordinates are integers, the optimal range is either 00 or the distance between two planets, so R2R^2 is always a non-negative integer; recover the range itself as R=R2R = \sqrt{R^2}.

Examples2

  1. Example 1

    Input
    4
    0 0 0 1
    0 1 0 0
    1 0 0 0
    1 1 0 1
    
    Expected output
    4
    1
    
  2. Example 2

    Input
    4
    0 0 0 1
    1 0 0 0
    0 1 0 0
    0 0 1 1
    
    Expected output
    0
    0