Cod sursa(job #1267072)

Utilizator hellol30FMI Macovei Daniel hellol30 Data 19 noiembrie 2014 14:54:57
Problema Cele mai apropiate puncte din plan Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 2.5 kb

import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.Arrays;
import java.util.Scanner;


class Main {
	
	static Punct[] array = null, copy= null;
	static int nrPuncte;
	static Scanner scanner = null; 
	
	private static double dist(Punct p1,Punct p2){
	    return (p1.getX()-p2.getX())*(p1.getX()-p2.getX())+(p1.getY()-p2.getY())*(p1.getY()-p2.getY());
	}
	private static double divide(int st,int dr){
	    if(dr-st<=2)
	        return Math.min(Math.min(dist(array[st],array[st+1]),dist(array[st],array[st+2])),dist(array[st+1],array[st+2]));
	    else{
	        int m=(st+dr)/2;
	        double d1=Math.min(divide(st,m),divide(m,dr));
	        double d2=d1;
	        for(int i=m ; i>=st && array[m].getX() - array[i].getX()<=d1 ; i--)
	            for(int j=1; j<=7 && i+j <= dr ; j++)
	                d2=Math.min(d2,dist(array[i],array[i+j]));
	        return d2;
	    }
	}
	
	public static void main(String args[]){
		
		try {
			scanner = new Scanner(new BufferedReader(new FileReader("cmap.in")));
			
			nrPuncte = scanner.nextInt();
			array = new Punct[nrPuncte];
			copy = new Punct[nrPuncte];
			
			for(int index = 0; index < nrPuncte; index++){
				
				int x = scanner.nextInt();
				int y = scanner.nextInt();
				array[index]= new Punct(x, y);
			}
			Arrays.sort(array);
			for(int index = 0; index < nrPuncte; index++)
				copy[index] = new Punct(array[index].getX(), array[index].getY());
			FileWriter g = new FileWriter(new File("cmap.out"));
			g.write( Math.sqrt(divide(0, nrPuncte -1)) +"\n");
			g.close();
		} catch (FileNotFoundException e) {
			System.out.println("Eroare Fisier!");
		} catch (IOException e) {
			System.out.println("Eroare Fisier!");
		}
	}
	static class Punct implements Comparable<Punct>{
		private int x,y;

		public Punct() {
			x = 0; 
			y = 0;
		}

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

		public Punct(double x, double y) {
			this.x = (int)x;
			this.y = (int)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;
		}

		@Override
		public int compareTo(Punct a) {
			if(x < a.x)
				return -1;
			if(x > a.x)
				return 1;
			if(y< a.y)
				return -1;
			if(y>a.y)
				return 1;
			return 0;
		}
	}
}