Cod sursa(job #1534163)

Utilizator dorumusuroiFMI - Doru Musuroi dorumusuroi Data 23 noiembrie 2015 14:05:53
Problema Cele mai apropiate puncte din plan Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 3.49 kb
package cmap;

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



class Punct implements Comparable<Punct>{
	public int x;
	public int y;
	Punct(){}
	Punct(int x, int y){
		this.x = x;
		this.y = y;
	}
	Punct(Punct p){
		this.x = p.x;
		this.y = p.y;
	}
	@Override
	public int compareTo(Punct p){
		if(this.x < p.x)
			return -1;
		if(this.x == p.x && this.y < p.y)
			return -1;
		return 1;
	}
	@Override
	public String toString(){
		return "(" + x + ";" + y + ")";
	}
	public int compareY(Punct p){
		if(this.y < p.y)
			return -1;
		if(this.y == p.y && this.x < p.x)
			return -1;
		return 1;
	}
	public double getDistance(Punct p){
		return Math.sqrt((double)(this.x-p.x)*(double)(this.x - p.x) + (double)(this.y - p.y) * (double)(this.y - p.y));
	}
	public void copy(Punct p){
		if(p == null){
			this.x = 0;
			this.y = 0;
		}
		this.x = p.x;
		this.y = p.y;
	}
}
public class Main {
	static ArrayList<Punct> puncte = new ArrayList<>();
	static Punct ans1 = new Punct(0,0), ans2 = new Punct(0,0);
	static void read(Scanner in){
		int n = in.nextInt();
		for(int i = 0; i < n; ++i)
			puncte.add(new Punct(in.nextInt(), in.nextInt()));
	}
	
	static double getClosestPoints(int lo, int hi){
		if(hi - lo <= 2){
			double dmin = Double.MAX_VALUE, d;
			for(int i = lo; i <= hi; ++i){
				for(int j = i+1; j <= hi; ++j){
					d = puncte.get(i).getDistance(puncte.get(j));
					if(d < dmin){
						dmin = d;
						if(dmin < ans1.getDistance(ans2)){
							ans1.copy(puncte.get(i));
							ans2.copy(puncte.get(j));
						}
					}
				}
			}
			Punct p = new Punct(0,0);
			for(int i = lo; i <= hi; ++i){
				for(int j = i+1; j <= hi; ++j){
					if(puncte.get(i).compareY(puncte.get(j)) > 0){
						p.copy(puncte.get(i));
						puncte.get(i).copy(puncte.get(j));
						puncte.get(j).copy(p);
					}
				}
			}
			return dmin;
		}
		int mid = (lo+hi)/2;
		double d1 = getClosestPoints(lo, mid);
		double d2 = getClosestPoints(mid+1, hi);
		double d = Math.min(d1, d2);
		int centru = puncte.get(mid).x;
		//au venit sortate, trebuie interclasate
		ArrayList<Punct> sortate = new ArrayList<>();
		for(int i = lo, j = mid + 1; j <= hi || i <= lo;){
			if(j > hi ||(i <= lo && puncte.get(i).compareY(puncte.get(j)) < 0)){
				sortate.add(puncte.get(i++));
			}
			else
				sortate.add(puncte.get(j++));
		}
		ArrayList<Punct> inBanda = new ArrayList<>();
		for(Punct p : sortate){
			if(p.x >= centru - d && p.x <= centru + d)
				inBanda.add(p);
		}
		int puncteInBanda = inBanda.size();
		for(int i = 0; i < puncteInBanda; ++i){
			for(int j = i+1; j < puncteInBanda && j < i+7 && inBanda.get(j).y < inBanda.get(i).y + d; ++j){
				d1 = inBanda.get(j).getDistance(inBanda.get(i));
				if(d1 < d){
					d = d1;
					if(d < ans1.getDistance(ans2)){
						ans1.copy(inBanda.get(i));
						ans2.copy(inBanda.get(j));
					}
				}
			}
		}
		return d;
	}
	public static void main(String[] args) throws FileNotFoundException{
		File inputFile = new File("cmap.in");
		File outputFile = new File("cmap.out");
		Scanner input = new Scanner(inputFile);
		read(input);
		input.close();
		if(puncte.size() > 1){
			ans1.copy(puncte.get(0));
			ans2.copy(puncte.get(1));
		}
		Collections.sort(puncte);
		PrintWriter out = new PrintWriter(outputFile);

		out.println(getClosestPoints(0, puncte.size()-1));
		out.close();
	}
}