Cod sursa(job #1821993)

Utilizator rangerChihai Mihai ranger Data 4 decembrie 2016 00:24:02
Problema Cele mai apropiate puncte din plan Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 3.55 kb
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileWriter;
import java.io.IOException;
import java.io.Writer;
import java.util.Arrays;
import java.util.Scanner;

class Point implements Comparable<Point>{
	int x, y;
	Point(){}
	Point(int _x, int _y){x = _x; y = _y;}
	
	public int compareTo(Point ot){
		return x - ot.x;
	}
	public String toString(){
		return x + " " + y;
	}
}

class Solution
{
	Point firstPoint, secondPoint;
	double minDist;
	
	private double dist(Point a, Point b){
		return Math.sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
	}
	
	class RetType{
		double minDist;
		Point firstPoint;
		Point secondPoint;
		RetType(double a, Point b, Point c){
			minDist = a;
			firstPoint = b;
			secondPoint = c;
		}
	}
	
	private RetType getMinDist(Point[] points, int l, int r){
		double _minDist = Double.MAX_VALUE;
		Point _firstPoint = null;
		Point _secondPoint = null;
		int n = l - r + 1;
		if (n <= 3){
			for(int i=l; i<=r; i++)
				for(int j=i+1; j<=r; j++)
				{
					double d = dist(points[i], points[j]);
					if (d < _minDist)
					{
						_minDist = d;
						_firstPoint = points[i];
						_secondPoint = points[j];
					}
				}
			// sort according to y coordinate
			for(int i=l;i<=r;i++)
				for(int j=i+1;j<=r;j++)
					if (points[i].y > points[j].y)
					{
						Point tmp = points[i];
						points[i] = points[j];
						points[j] = tmp;
					}
			return new RetType(_minDist, _firstPoint, _secondPoint);
		}
		
		int med = (l + r) / 2;
		int VerticalLine = points[med].x;
		RetType ret1 = getMinDist(points, l, med);
		RetType ret2 = getMinDist(points, med + 1, r);
		if (ret1.minDist > ret2.minDist) 
			ret1 = ret2; 

		double d = ret1.minDist;
		_minDist = d;
		_firstPoint = ret1.firstPoint;
		_secondPoint = ret2.secondPoint;
		
		// merge the two halves of array points[]
		Point[] new_Points = new Point[r - l + 1];
		int i = l, j = med + 1, k = 0;
		while(i < med && j < r) {
			if (points[i].y < points[j].y) {
				new_Points[k] = points[i]; k++; i++;
			} else {
				new_Points[k] = points[j]; k++; j++;
			}
		}
		while(i < med) new_Points[k++] = points[i++];
		while(j < r) new_Points[k++] = points[j++];
		k = 0;
		for(i = l; i <= r; i++){
			points[i] = new_Points[k++]; 
		}
		// end of merge
		
		k = 0;
		for(i=l; i <= r; i++){
			if (Math.abs(points[i].x - VerticalLine) < d)
				new_Points[k++] = points[i];
		}
		
		for(i=0; i<k; i++){
			j = i + 1;
			while(j < k && new_Points[j].y - new_Points[i].y < d) {
				double dis = dist(new_Points[i], new_Points[j]);
				if (dis < _minDist) 
				{
					_minDist = dis;
					_firstPoint = new_Points[i];
					_secondPoint = new_Points[j];
				}
				j += 1;
			}
		}
		return new RetType(_minDist, _firstPoint, _secondPoint);
		
	}
	
	double GetMinDist(Point[] points){
		Arrays.sort(points);
		
		RetType rt = getMinDist(points,0, points.length - 1);
		firstPoint = rt.firstPoint;
		secondPoint = rt.secondPoint;
		minDist = rt.minDist;
		
		return minDist;
	}
}

public class Main {
	public static void main(String[] args) throws IOException{
		Scanner input = new Scanner(new File("cmap.in"));
		
		int n = input.nextInt();
		Point[] points = new Point[n];
		for(int i=0; i<n; i++){
			points[i] = new Point(input.nextInt(), input.nextInt());
		}
		
		Solution s = new Solution();
		double distMin = s.GetMinDist(points);
		Writer wr = new FileWriter("cmap.out");
		wr.write(String.valueOf(distMin));
		
		wr.close();
		input.close();
	}
}