import java.util.ArrayList;
import java.util.Collection;
import java.util.List;

public class Bsp {

    public static void main(String... args) {
        List<Point> points = new ArrayList<Point>();
        points.add(new Point(0, 0, 0, 2));
        points.add(new Point(1, 3, 0, 2));
        points.add(new Point(2, 4, 0, 1));

        Node node = new Node(points);
        node.collide();
    }

    public static void collide(Point other, Point point) {
        if (point.collides(other))
            System.out.println(point.id + " " + other.id);
    }
}

class Point {
    public final int id;
    public final double x, y, r;

    Point(int id, double x, double y, double r) {
        this.id = id;
        this.x = x;
        this.y = y;
        this.r = r;
    }

    public boolean isBound(double left, double top, double right, double bottom) {
        return x - r >= left && x + r < right && y - r >= top && y + r < bottom;
    }

    public boolean collides(Point other) {
        double dx = x - other.x;
        double dy = y - other.y;
        double dr = r + other.r;
        return dx * dx + dy * dy < dr * dr;
    }
}

class Node {
    private List<Point> points;
    private final double l, t, r, b;
    private Node n1;
    private Node n2;

    public Node(Collection<Point> allPoints) {
        double l = Double.MAX_VALUE, t = Double.MAX_VALUE, r = -Double.MAX_VALUE, b = -Double.MAX_VALUE;
        for (Point point : allPoints) {
            l = Math.min(point.x - point.r, l);
            r = Math.min(point.x + point.r, r);
            t = Math.min(point.y - point.r, t);
            b = Math.min(point.y + point.r, b);
        }
        this.l = l;
        this.t = t;
        this.r = r;
        this.b = b;
        split(allPoints);
    }

    public Node(double l, double t, double r, double b) {
        this.l = l;
        this.t = t;
        this.r = r;
        this.b = b;
    }

    public void collide() {

        for (int i = 0, j = points.size(); i < j; i++) {
            Point point = points.get(i);
            for (int k = i+1; k < j; k++)
                Bsp.collide(point, points.get(k));

            if (n1 != null) n1.collide(point);
            if (n2 != null) n2.collide(point);
        }
        if (n1 != null) n1.collide();
        if (n2 != null) n2.collide();
    }

    private void collide(Point other) {
        for (Point point : points)
            Bsp.collide(other, point);
    }



    public void split(Collection<Point> pts) {
        points = new ArrayList<Point>();
        Node n1;
        Node n2;
        if (r - l > b - t) {
            n1 = new Node(l, t, (l + r) / 2, b);
            n2 = new Node((l + r) / 2, t, r, b);
        } else {
            n1 = new Node(l, t, r, (b + t) / 2);
            n2 = new Node(l, (b + t) / 2, r, b);
        }

        List<Point> list1 = new ArrayList<Point>();
        List<Point> list2 = new ArrayList<Point>();

        for (Point point : pts) {
            if (n1.contains(point))
                list1.add(point);
            else if (n2.contains(point))
                list2.add(point);
            else
                points.add(point);
        }

        if (list1.size() > 0) {
            n1.split(list1);
            this.n1 = n1;
        }

        if (list2.size() > 0) {
            n2.split(list2);
            this.n2 = n1;
        }
    }

    public boolean contains(Point point) {
        return point.isBound(l, t, r, b);
    }
}