Cod sursa(job #1276221)

Utilizator cata25Matei Catalin Daniel cata25 Data 26 noiembrie 2014 02:16:36
Problema Cele mai apropiate puncte din plan Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 1.93 kb
package DistantaMinimaPuncte;

import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.util.Scanner;



class Punct implements Comparable<Punct>{
	
	  long x, y;
	  public double dist(Punct P){
		  return Math.sqrt(Math.pow(x-P.x, 2)+Math.pow(y-P.y,2));  
	  }
	  Punct(long a, long b){
		  x=a;
		  y=b;
	  }
		@Override
		public int compareTo(Punct P) {
			if(x==P.x)
				return (int)(y-P.y);
			return (int)(x-P.x);
		}
	}


class Main {
	
	static Punct V[], A;
	static double dmin=Double.MAX_VALUE;
	
	static void mediana(int a, int b, int  k)
	{
	    int i=a, j=b; 
	    Punct p=V[(a+b)/2];

	    while(i <= j)
	    {
	        while(V[i].compareTo(p)<0) i++;
	        while(V[j].compareTo(p)>0) j--;

	        if(i <= j)
	        {
	            Punct aux = V[i]; 
	            V[i] = V[j];
	            V[j] = aux;
	            i++;
	            j--;
	        }
	    }

	    if      (k <= j) mediana(a,j,k);
	    else if (k >= i) mediana(i,b,k);
	}
	
	static void Search(int p, int u){
		if((u-p+1)>1){
			int poz=(u-p+1)/2+p;
			mediana(p, u, poz);
			if(A.compareTo(V[poz])==0);
			else{
				
				if(V[poz].dist(A)<dmin){
					dmin=V[poz].dist(A);
				}
					if(A.compareTo(V[poz])<0)
					Search(p,poz-1);
				else if(A.compareTo(V[poz])>0)
					Search(poz+1, u);
			}
		}
		else 
			if(A.compareTo(V[p])==0);
			else
				if(V[p].dist(A)<dmin){
					dmin=V[p].dist(A);
				}
			
			
	}

	public static void main(String[] args) throws FileNotFoundException {
		Scanner sc=new Scanner(new File("cmap.in"));
		long n= sc.nextLong();
		V= new Punct[(int) n];
		for(int i=0; i<n;i++)
			V[i]= new Punct(sc.nextLong(), sc.nextLong());
		for(int i=0;i<n;i++){
			A=new Punct(V[i].x, V[i].y);
			Search(0,(int) (n-1));
		}
		PrintWriter pr= new PrintWriter(new File("cmap.out"));
		pr.print(dmin);
		sc.close();
		pr.close();
	}

}