Cod sursa(job #1821321)

Utilizator HorridSaracin Mihnea Horrid Data 2 decembrie 2016 21:46:07
Problema Cele mai apropiate puncte din plan Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 2.79 kb
import java.util.*;
import java.io.*; 



public class Main {
	static class Pair {
	private int x,y;

	public int getX() {
		return x;
	}
	public void setX(int x) {
		this.x = x;
	}
	public int getY() {
		return y;
	}
	public void setY(int y) {
		this.y = y;
	}
	public Pair() {
		x=0;y=0;
	}
	public Pair (int s,int r) {
		x=s;
		y=r;

	}
	public String toString() {
		return "("+x+","+y+")";
	}
}

	
	static ArrayList<Pair> X;
	static Pair minPair[];
	public static void main(String[] args)throws IOException {
	
		Scanner sc=null;
		FileWriter out=null;
		
		try{	
		ArrayList<Pair> a=new ArrayList<>();
		sc=new Scanner(new File("cmap.in"));
		out=new FileWriter(new File("cmap.out"));
		int n=sc.nextInt();
		X=new ArrayList<>();
		
		minPair=new Pair[2];
		minPair[0]=new Pair();
		minPair[1]=new Pair();
		
		for(int i=0;i<n;++i)
		{
			int x=sc.nextInt();
			int y=sc.nextInt();
			a.add(new Pair(x,y));
			X.add(new Pair(x,y));
		}
	//	Collections.sort(a,(i,j)->i.getY()-j.getY());
		//Collections.sort(X,(i,j)->i.getX()-j.getX());
		Collections.sort(a,new Comparator<Pair>(){
			
			 public int compare(Pair i, Pair j) {
        return i.getY()-j.getY();
			 }
				
		});
		Collections.sort(X,new Comparator<Pair>(){
			
			 public int compare(Pair i, Pair j) {
        return i.getX()-j.getX();
			 }
				
		});
	
		out.write(""+Math.sqrt((double)Di(0, a.size()-1, a))+"\n");
		
	//	for(int i=0;i<2;++i)
		//	out.write(minPair[i]+" ");
		

		
	} catch (FileNotFoundException e) {
		System.out.println("Fisier intrare inexistent");
	}
	if(sc!=null)	sc.close();
	if(out!=null)	out.close();
	}
	static int dist(Pair a,Pair b)
	{
		    return (a.getX() - b.getX()) * (a.getX() - b.getX()) + (a.getY()-b.getY())*(a.getY()-b.getY());
	}
	
	static int Di(int st,int dr,ArrayList<Pair> Y)
	{
		int d=Integer.MAX_VALUE;
		if(dr-st+1<=3){
			for(int i=st;i<dr;++i)
				for(int j=i+1;j<=dr;++j){
					int dist1=dist(X.get(i), X.get(j));
					if(dist1<d)	{
									d=dist1;
									minPair[0].setX(X.get(i).getX());
									minPair[0].setY(X.get(i).getY());
									minPair[1].setX(X.get(j).getX());
									minPair[1].setY(X.get(j).getY());
								}
				}	
			}
		else {
		
		int mid=(st+dr)/2;
		d=Math.min(Di(st,mid,Y),Di(mid+1,dr,Y));
		ArrayList<Pair> v=new ArrayList<>();
		for(int i=st;i<=dr;++i)
				if(Math.abs(Y.get(i).getX()-X.get(mid).getX())<=d)
					v.add(Y.get(i));
		for(int i=0;i<v.size()-7;++i)
			for(int j=i+1;j<=i+7;++j){	
				int dist1=dist(v.get(i), v.get(j));
				if(dist1<d)	{
					d=dist1;
					minPair[0].setX(v.get(i).getX());
					minPair[0].setY(v.get(i).getY());
					minPair[1].setX(v.get(j).getX());
					minPair[1].setY(v.get(j).getY());
				}
			}
		
		}
	
		return d;
		
	}
	
}