Pagini recente » Cod sursa (job #405263) | Cod sursa (job #393071) | Cod sursa (job #1185589) | Cod sursa (job #299737) | Cod sursa (job #1279970)
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 DistMin
{
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(puncteX, new Comparator<Point>(){
public int compare(Point a, Point b){
return a.x - b.x;
}});
//Collections.sort(puncteY, (Point a, Point b)->
//{
// return a.y - b.y;
//});
Collections.sort(puncteY, new Comparator<Point>(){
public int compare(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;
//});
puncteX.get(i).py = Collections.binarySearch(puncteY, puncteX.get(i), new Comparator<Point>(){
public int compare(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(end - beg < 2)
return Double.MAX_VALUE;
if(end - beg <= 3)
{
double min;
double alpha = getdistance(puncteX.get(beg), puncteX.get(beg+1));
if(end - beg == 3)
{
double beta = getdistance(puncteX.get(beg), puncteX.get(beg+2));
double theta = getdistance(puncteX.get(beg+1), puncteX.get(beg+2));
min = alpha < beta ? alpha : beta;
min = theta < min ? theta : min;
}
else
min = alpha;
return min;
}
int linie = beg + (end - beg) / 2;
double d1 = dist(puncteX, puncteY, beg, linie);
double d2 = dist(puncteX, puncteY, linie, end);
double min = d1 < d2 ? d1 : d2;
double d3 = getd3(puncteX, puncteY, beg, end, linie, min);
return d3 < min ? d3 : 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;
}
}