Cod sursa(job #1289889)

Utilizator tudor.rotarusTudor Rotarus tudor.rotarus Data 10 decembrie 2014 14:58:18
Problema Cele mai apropiate puncte din plan Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 2.4 kb

import java.io.FileInputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	static Scanner sc;
	static Punct[] p,copy;
	static PrintWriter iesire;
	static int n;

	
	
	static void Merge(int st,int dr)
	{
		Punct aux[] = new Punct[dr-st+1];
		int m=(st+dr)/2;
		int i=st,j=m+1,k=0;
		while(i<=m && j<=dr)
		{
			if(p[i].getX()<p[j].getX())
			{
				aux[k++]=p[i++];
			}
			else
			{
				aux[k++]=p[j++];
			}
		}
		while(i<=m)
		{
			aux[k++]=p[i++];
		}
		while(j<=dr)
		{
			aux[k++]=p[j++];
		}
		
		for(i=st,k=0;i<=dr;i++,k++)
		{
			p[i]=aux[k];
		}
	}
	
	
	static double divide(int s,int d)
	{
		Punct aux[] = new Punct[d-s+1];
		if(d-s<=2)
		{
			Merge(s,d-1);
			Merge(s,d);
			if(d-s==2)
				return Math.min(Math.min(p[s].distanta(p[s+1]), p[s].distanta(p[s+1])), p[s+1].distanta(p[s+2]));
			else return Math.min(p[s].distanta(p[s+1]), p[s].distanta(p[s+1]));
			
		}
		int m= (s+d)/2;
		double dist=Math.min(divide(s,m),divide(m+1,d));
		double inter=dist;
		
		Merge(s,d);
		
		int k=0;
		for(int i=s;i<=d;i++)
		{
			if(Math.abs(p[i].getY()-copy[m].getY())<inter)
			{
				aux[k++]=p[i];
			}
		}
		
		for(int i=0;i<k-1;i++)
		{
			for(int j=i+1;j<k && j<8;j++)
			{
				inter=Math.min(inter, p[i].distanta(p[j]));
			}
		}
        return inter;
		
	}
	
	public static void main(String[] args) throws Exception
	{

			sc=new Scanner(new FileInputStream("cmap.in"));
			n = sc.nextInt();
			p = new Punct[n];
			copy = new Punct[n];
			for(int i=0;i<n;i++)
			{
				int x = sc.nextInt();
				int y = sc.nextInt();
				p[i] = new Punct(x,y);
			}
			Arrays.sort(p);
			for(int i=0;i<n;i++)
			{
				copy[i]=p[i];
			}
				
			iesire = new PrintWriter("cmap.out");
			iesire.printf("%.6f" , Math.sqrt(divide(0,n-1)));
			iesire.close();  
	}

}


class Punct implements Comparable<Punct> {

	double x,y;

	public Punct(double x, double y) {
		super();
		this.x = x;
		this.y = y;
	}

	public double getX() {
		return x;
	}

	public double getY() {
		return y;
	}

	
	public double distanta(Punct a)
	{
		return (x-a.getX())*(x-a.getX())+(y-a.getY())*(y-a.getY());
	}

	public int compareTo(Punct o) {
		if(y<o.y)
			return -1;
		if(y>o.y)
			return 1;
		return 0;
	}
	
	public String toString()
	{
		return "[" + x + "," + y + "] ";
	}
}