Cod sursa(job #1825973)

Utilizator zelmoatisTatuta Ionut-Catalin zelmoatis Data 9 decembrie 2016 22:00:27
Problema Cele mai apropiate puncte din plan Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 6.26 kb
package closestpair;

import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Scanner;

class byX implements Comparator<Point>{
    @Override
    public int compare(Point o1, Point o2){
        return ( o1.getx() == o2.getx() )?0:( ( o1.getx() > o2.getx() )?1:-1 );
    }    
}
class byY implements Comparator<Point>{
    @Override
    public int compare(Point o1, Point o2){
        return ( o1.gety() == o2.gety() )?0:( ( o1.gety() > o2.gety() )?1:-1 );
        
    }
}

class Point{
    private Integer id;
    private double x;
    private double y;
    public Point(){
        x=0;
        y=0;
    }
    public Point( Point other ){
        x = other.getx();
        y = other.gety();
        id = other.getid();
    }
    public Point(double x1,double y1, Integer i){
        x = x1;
        y = y1;
        id = i;
    }
    public double getx(){
        return x;
    }
    public double gety(){
        return y;
    }
    public Integer getid(){
        return id;
    }
    public double dist( Point other ){
        return Math.sqrt( (x-other.getx())*(x-other.getx()) + (y-other.gety())*(y-other.gety() ) );
    }
    @Override
    public String toString(){
        return id + ": (" + x + ", " + y + ")";
    }
}
class Segment{
    private Point p1;
    private Point p2;
    private double dist;
    public Segment(Point o1, Point o2){
        p1 = new Point(o1);
        p2 = new Point(o2);
        dist = p1.dist(p2);
    }
    public Segment( Segment o){
        p1 = o.p1;
        p2 = o.p2;
        dist = o.dist;
    }
    public double getDist(){
        return dist;
    }
    public Point getP1(){
        return p1;
    }
    public Point getP2(){
        return p2;
    }
}
class ClosestPair {
    public static Segment minDist(ArrayList<Point> P,  ArrayList<Integer> Px){
        if( Px.size() == 2 )
            return new Segment( P.get(Px.get(0)), P.get(Px.get(1)) );
        Segment s1,s2,s3;
        s1 = new Segment( P.get(Px.get(0)), P.get(Px.get(1)) );
        s2 = new Segment( P.get(Px.get(1)), P.get(Px.get(2)) );
        s3 = new Segment( P.get(Px.get(2)), P.get(Px.get(0)) );
        if(s1.getDist()>s2.getDist()){
            if(s1.getDist()>s3.getDist()){
                return s1;
            } else {
                return s3;
            }
        } else {
            if(s2.getDist()>s3.getDist()){
                return s2;
            } else {
                return s3;
            }
        }
    }
    
    public static Segment Closest1(ArrayList<Point> P){
        ArrayList<Point> Ord = new ArrayList<>();
        Ord = cp(P);
        int i, n = Ord.size();
        Collections.sort(Ord, new byX());
        ArrayList<Integer> Px = new ArrayList<>(n);
        for( i = 0; i < n; i ++ ){
            Px.add(Ord.get(i).getid());
        }
        Collections.sort(Ord, new byY());
        ArrayList<Integer> Py = new ArrayList<>(n);
        for( i = 0; i < n; i ++ ){
            Py.add(Ord.get(i).getid());
        }
        return Closest2(P, Px, Py);
    }
    public static Segment Closest2(ArrayList<Point> P,  ArrayList<Integer> Px,  ArrayList<Integer> Py){
        if(Px.size()<=3)
            return minDist(P,Px);//verificam distantele dintre elementele care apar in px
        ArrayList<Integer> Qx, Qy, Rx, Ry;
        Qx = new ArrayList<>();
        Qy = new ArrayList<>();
        Rx = new ArrayList<>();
        Ry = new ArrayList<>();
        int i, n = Px.size();
        for( i = 0; i < n; i ++ ){
            if( i < n/2 ){
                Qx.add(Px.get(i));
            } else {
                Rx.add(Px.get(i));
            }
        }
        for( i = 0; i < n; i ++ ){
            if( P.get( Py.get(i) ).getx() < P.get( Px.get(n/2) ).getx() ){
                Qy.add(Py.get(i));
            } else {
                Ry.add(Py.get(i));
            }
        }
        Segment d1, d2, d;
        d1 = Closest2(P, Qx, Qy);
        d2 = Closest2(P, Rx, Ry);
        d = d1.getDist() < d2.getDist()?d1:d2;
        double mid = ( P.get( Px.get(n/2 - 1) ).getx() + P.get( Px.get(n/2) ).getx() )/2;
        ArrayList<Integer> Sy = new ArrayList<>();
        for( i = 0; i < n; i ++ ){
            double xpos = P.get( Py.get(i) ).getx();
            if( ( xpos < mid && xpos > mid - d.getDist() ) || ( xpos > mid && xpos < mid + d.getDist() ) ){
                Sy.add(Py.get(i));
            }
        }
        if(Sy.size()<2)
            return d;
        Segment ds = new Segment( P.get(Sy.get(0)), P.get(Sy.get(1)) );
        n = Sy.size();
        for( i = 0; i < n; i ++ ){
            int m = Math.min(i+15, n-1);
            Segment dtemp;
            
            if(i + 2 == n){
                dtemp = new Segment( P.get(Sy.get(i)), P.get(Sy.get(i+1)) );
                if(dtemp.getDist() < ds.getDist())
                    ds = new Segment(dtemp);
                break;
            }
            int j;
            for( j = i+1; j <= m; j ++ ){
                dtemp = new Segment( P.get(Sy.get(i)), P.get(Sy.get(j)) );
                if(dtemp.getDist() < ds.getDist())
                    ds = new Segment(dtemp);
            }
        }
        if(d.getDist() < ds.getDist())
            return d;
        else
            return ds;
    }
     
    public static ArrayList<Point> cp(ArrayList<Point> O){
        ArrayList<Point> N = new ArrayList<>();
        int i, n = O.size();
        for( i = 0; i < n; i ++ ){
            Point pt = new Point(O.get(i));
            N.add(pt);
        }
        
        return N;
    }
    public static void main(String[] args) throws FileNotFoundException{
        ArrayList<Point> Points = new ArrayList<>();
        Scanner fsc = new Scanner(new File("cmap.in"));
        int i, n;
        n = fsc.nextInt();
        for( i = 0; i < n; i ++ ){
            Point pt = new Point(fsc.nextInt(),fsc.nextInt(),i);
            Points.add(pt);
        }
        Segment result = new Segment(Closest1(Points));
        PrintWriter pwf = new PrintWriter("cmap.out");
        pwf.print(result.getDist());
        pwf.close();
    }
    
}