Pagini recente » Cod sursa (job #1723545) | Cod sursa (job #902025) | Cod sursa (job #1777284) | Cod sursa (job #3201895) | Cod sursa (job #1275459)
import java.util.Scanner;
import java.io.*;
import java.util.ArrayList;
import java.util.Collections;
class Point
{
public int x, y;
public int px, py;
}
class DistMin2
{
public static void main(String[] args)
{
ArrayList<Point> puncteX = new ArrayList<Point>();
ArrayList<Point> puncteY = new ArrayList<Point>();
try
{
Scanner sc = new Scanner(new java.io.File("cmap.in"));
int n;
n = sc.nextInt();
//puncte = new Point[n];
for(int i = 0; i < n; i++)
{
Point p = new Point();
p.x = sc.nextInt();
p.y = sc.nextInt();
puncteX.add(p);
puncteY.add(p);
}
sc.close();
//apel catre functia de det
Collections.sort(puncteX, (Point a, Point b)->
{
return a.x - b.x;
});
Collections.sort(puncteY, (Point a, Point b)->
{
return a.y - b.y;
});
for(int i = 0; i < puncteX.size(); i++)
{
puncteX.get(i).py = Collections.binarySearch(puncteY, puncteX.get(i), (Point a, Point b) ->
{
return a.y - b.y;
});
puncteY.get(puncteX.get(i).py).px = i;
}
PrintWriter pw = new PrintWriter(new FileWriter(new File("cmap.out")));
pw.println(dist(puncteX, puncteY , 0, puncteX.size()));
//for(int i = 0; i < n; i++)
//{
// pw.println(puncte.get(i).x + " " +puncte.get(i).y);
//}
pw.close();
}
catch(Exception ex)
{
System.out.println("404");
}
}
static double getdistance(Point a, Point b)
{
double x = a.x - b.x;
x *= x;
double y = a.y - b.y;
y *= y;
return Math.sqrt(x + y);
}
static double dist(ArrayList<Point> puncteX, ArrayList<Point> puncteY, int beg, int end)
{
if(beg - end < 2)
return Double.MAX_VALUE;
if(beg - end < 3)
{
return getdistance(puncteX.get(beg), puncteX.get(beg+1));
}
int linie = (end - beg) / 2;
double d1 = dist(puncteX, puncteY, beg, linie);
double d2 = dist(puncteX, puncteY, linie, end);
double min = d1 < d2 ? d1 : d2;
return getd3(puncteX, puncteY, beg, end, linie, min);
}
static double getd3(ArrayList<Point> puncteX, ArrayList<Point> puncteY, int beg, int end, int linie, double min)
{
ArrayList<Point> banda = new ArrayList<Point>();
ArrayList<Point> bandaY = new ArrayList<Point>();
boolean[] shouldadd = new boolean[puncteX.size()];
int pozlinie = puncteX.get(linie).x;
for(int i = beg; i < end; i++)
{
shouldadd[puncteX.get(i).py] = false;
double distLine = puncteX.get(i).x - pozlinie;
if(distLine < 0)
distLine *= -1;
if(distLine <= min)
{
banda.add(puncteX.get(i));
shouldadd[puncteX.get(i).py] = true;
}
}
for(int i = 0; i < puncteX.size(); i++)
{
if(shouldadd[i])
{
bandaY.add(puncteY.get(i));
}
}
for(int i = 0; i < bandaY.size(); i++)
{
int limit = 15 < bandaY.size() - i - 1 ? 15 : bandaY.size() - i - 1;
for(int j = 1; j <= limit; j++)
{
double dist = getdistance(bandaY.get(i), bandaY.get(i+j));
if(dist < min)
{
min = dist;
}
}
}
return min;
}
}