Test

import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.Random;


public class Main {

    /**
     * Один метр в градусах,
     */
    private final double DEG = 0.000001;

    public final class Zone {
        public int id;
        public double x;
        public double y;
        public double r;

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


    }

    class XComparator implements Comparator {

        public int compare(Object obj1, Object obj2){
            Zone zone1 = (Zone)obj1;
            Zone zone2 = (Zone)obj2;
            double x1 = zone1.x - zone1.r;
            double x2 = zone2.x - zone2.r;

            if(x1 > x2)
                return 1;
            else if(x1 < x2)
                return -1;
            else
                return -1;
        }

    }

    class BComparator implements Comparator {

        public int compare(Object obj1, Object obj2){
            Zone zone = (Zone)obj1;
            Zone point = (Zone)obj2;
            double bx = zone.x - zone.r;
            double px = point.x ;

            if(bx < px)
                return 1;
            else if(bx > px)
                return -1;
            else
                return -1;
        }

    }

    private LinkedList<Zone> map_x;

    private XComparator xComparator = new XComparator();
    private BComparator comparator = new BComparator();

    private double boffset_x = 0;
    private double boffset_y = 0;

    private double eoffset_x = 0;
    private double eoffset_y = 0;


    public static void main(String[] args) {

        Main man = new Main();
        Random randomGenerator = new Random();
        long start = System.currentTimeMillis();
        int i = 0;
        while(i < 100000) {
            man.addZone(i,randomGenerator.nextInt(359)+randomGenerator.nextDouble(), randomGenerator.nextInt(359)+randomGenerator.nextDouble(), randomGenerator.nextInt(10000));
            i++;
        }
        start = System.currentTimeMillis() - start;
        System.out.println("Gen:" + start);
        start = System.currentTimeMillis();
        while(i < 250) {

            man.probe(randomGenerator.nextInt(359)+randomGenerator.nextDouble(), randomGenerator.nextInt(359)+randomGenerator.nextDouble());
            i++;

        }
        start = System.currentTimeMillis() - start;
        System.out.println("Probe:" + start);
        /*
        man.addZone(1, 25, 60, 15);
        man.addZone(2, 15, 40, 10);
        man.addZone(3, 25, 20, 20);
        man.addZone(4, 35, 40, 15);
        man.addZone(5, 40, 60, 10);

        man.probe(30, 30);
        */
    }

    public Main() {
        map_x = new LinkedList<Main.Zone>();
    }

    private double convert(int r) {
        return r*DEG;
    }

    public void addZone(int id, double x, double y, int r) {
        double nr = convert(r);
        Zone zone = new Zone(id,x,y,nr);
        if(map_x.size() == 0) {
            map_x.add(zone);
        } else {
            int xId = Collections.binarySearch(map_x, zone, xComparator)*-1;
            map_x.add(xId-1, zone);
        }
        if(x-nr < 0)
            boffset_x = (x-nr)*-1;
        if(y-nr > 0)
            boffset_y = (y-nr)*-1;

        if(x+nr > 360)
            eoffset_x = 360 - x+nr;
        if(y+nr > 360)
            eoffset_y = 360 - y+nr;

    }

    public void probe(double x, double y) {
        System.out.println("Probe: (" + x + ":" + y + ")");

        Zone point = new Zone(0,x,y,0);

        int xId = Collections.binarySearch(map_x, point, comparator)*-1;

        for(int i = xId; i < map_x.size(); i++) {
            Zone check = map_x.get(i);
            if(check.x + check.r < x) break;
            if((x-check.x)*(x-check.x)+(y-check.y)*(y-check.y) <= check.r*check.r) {
                //System.out.println("Goal: " + check.id);
            }
        }

        if( x < eoffset_x) {
            x = x + 360;
        }
        if( y < eoffset_y) {
            y = y + 360;
        }
        if( 360 - x < boffset_x) {
            x = x + 360;
        }
        if( 360 -  x > boffset_x) {
            x = x + 360;
        }

        point = new Zone(0,x,y,0);

        xId = Collections.binarySearch(map_x, point, comparator)*-1;

        for(int i = xId; i < map_x.size(); i++) {
            Zone check = map_x.get(i);
            if(check.x + check.r < x) break;
            if((x-check.x)*(x-check.x)+(y-check.y)*(y-check.y) <= check.r*check.r) {
                //System.out.println("Goal: " + check.id);
            }
        }

    }

}