Pagini recente » Cod sursa (job #1000528) | Cod sursa (job #2561816) | Cod sursa (job #2453788) | Cod sursa (job #901604) | Cod sursa (job #1821993)
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();
}
}