Pagini recente » Cod sursa (job #2636676) | Cod sursa (job #952787) | Cod sursa (job #1041716) | Cod sursa (job #2818798) | Cod sursa (job #1820488)
import java.io.*;
import java.util.*;
class Point implements Comparable<Point>{
int x;
int y;
public Point(int x, int y){
this.x = x;
this.y = y;
}
public String toString(){
return "[" + x + ", " + y + "]";
}
public int compareTo(Point other){
return this.x - other.x;
}
}
public class Main {
public static ArrayList<Point> points = new ArrayList<Point>();
public static ArrayList<Point> pointsAux = new ArrayList<Point>();
public static ArrayList<Point> pointsMerged = new ArrayList<Point>();
public static 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));
}
public static double solveForThree(int ls, int ld){
if(ls == ld)
return 0;
double minDist = dist(points.get(ls), points.get(ls + 1));
double distance = 0;
for(int i = ls; i <= ld; i ++)
for(int j = ls + 1; j <= ld; j ++)
if(!points.get(i).equals(points.get(j))){
distance = dist(points.get(i), points.get(j));
if(distance < minDist)
minDist = distance;
}
return minDist;
}
public static double getShortestDistance(int ls, int ld){
if(ld - ls + 1 <= 3)
return solveForThree(ls, ld);
else{
int m = (ls + ld)/2;
double distStg = getShortestDistance(ls, m);
double distDr = getShortestDistance(m + 1, ld);
double distMin = Math.min(distStg, distDr);
for(int i = ls; i <= ld; i ++){
int dr = points.get(m).x;
Point current = points.get(i);
if(Math.abs(current.x - dr) < distMin)
pointsAux.add(current);
}
merge(pointsAux, pointsMerged);
for(int i = 0; i < pointsMerged.size(); i ++){
int maxIndex = Math.min(pointsMerged.size(),7);
for(int j = 0; j <maxIndex; j ++)
if(!pointsMerged.get(i).equals(pointsMerged.get(j)))
distMin = Math.min(distMin, dist(pointsMerged.get(i), pointsMerged.get(j)));
}
return distMin;
}
}
public static void merge(ArrayList<Point> points, ArrayList<Point> pointsMerged){
int i = 0, j = 0;
ArrayList<Point> aux = new ArrayList<Point>();
while(i < points.size() && j < pointsMerged.size()){
if(points.get(i).compareTo(pointsMerged.get(j)) < 0)
aux.add(points.get(i ++));
else
aux.add(pointsMerged.get(j ++));
}
while(i < points.size())
aux.add(points.get(i ++));
while(j < pointsMerged.size())
aux.add(pointsMerged.get(j ++));
pointsMerged = (ArrayList<Point>)aux.clone();
}
public static void main(String[] args) {
Scanner sc = null;
int n = 0;
try{
sc = new Scanner(new File("cmap.in"));
n = sc.nextInt();
for(int i = 0; i < n; i ++){
int a = sc.nextInt();
int b = sc.nextInt();
points.add(new Point(a,b));
}
}catch(Exception ex){
ex.printStackTrace();
}
finally{
sc.close();
}
Collections.sort(points, new Comparator<Point>(){
public int compare(Point A, Point B){
return A.x - B.x;
}
});
//System.out.println(getShortestDistance(0,n - 1));
try{
PrintWriter writer = new PrintWriter("cmap.out", "UTF-8");
writer.println(getShortestDistance(0,n - 1));
}catch(FileNotFoundException | UnsupportedEncodingException ex){
ex.printStackTrace();
}
}
}