Pagini recente » Istoria paginii runda/lot2006z3 | Istoria paginii olimpici | Cod sursa (job #2069456) | Istoria paginii runda/brasov_16/clasament | Cod sursa (job #1821321)
import java.util.*;
import java.io.*;
public class Main {
static class Pair {
private int x,y;
public int getX() {
return x;
}
public void setX(int x) {
this.x = x;
}
public int getY() {
return y;
}
public void setY(int y) {
this.y = y;
}
public Pair() {
x=0;y=0;
}
public Pair (int s,int r) {
x=s;
y=r;
}
public String toString() {
return "("+x+","+y+")";
}
}
static ArrayList<Pair> X;
static Pair minPair[];
public static void main(String[] args)throws IOException {
Scanner sc=null;
FileWriter out=null;
try{
ArrayList<Pair> a=new ArrayList<>();
sc=new Scanner(new File("cmap.in"));
out=new FileWriter(new File("cmap.out"));
int n=sc.nextInt();
X=new ArrayList<>();
minPair=new Pair[2];
minPair[0]=new Pair();
minPair[1]=new Pair();
for(int i=0;i<n;++i)
{
int x=sc.nextInt();
int y=sc.nextInt();
a.add(new Pair(x,y));
X.add(new Pair(x,y));
}
// Collections.sort(a,(i,j)->i.getY()-j.getY());
//Collections.sort(X,(i,j)->i.getX()-j.getX());
Collections.sort(a,new Comparator<Pair>(){
public int compare(Pair i, Pair j) {
return i.getY()-j.getY();
}
});
Collections.sort(X,new Comparator<Pair>(){
public int compare(Pair i, Pair j) {
return i.getX()-j.getX();
}
});
out.write(""+Math.sqrt((double)Di(0, a.size()-1, a))+"\n");
// for(int i=0;i<2;++i)
// out.write(minPair[i]+" ");
} catch (FileNotFoundException e) {
System.out.println("Fisier intrare inexistent");
}
if(sc!=null) sc.close();
if(out!=null) out.close();
}
static int dist(Pair a,Pair b)
{
return (a.getX() - b.getX()) * (a.getX() - b.getX()) + (a.getY()-b.getY())*(a.getY()-b.getY());
}
static int Di(int st,int dr,ArrayList<Pair> Y)
{
int d=Integer.MAX_VALUE;
if(dr-st+1<=3){
for(int i=st;i<dr;++i)
for(int j=i+1;j<=dr;++j){
int dist1=dist(X.get(i), X.get(j));
if(dist1<d) {
d=dist1;
minPair[0].setX(X.get(i).getX());
minPair[0].setY(X.get(i).getY());
minPair[1].setX(X.get(j).getX());
minPair[1].setY(X.get(j).getY());
}
}
}
else {
int mid=(st+dr)/2;
d=Math.min(Di(st,mid,Y),Di(mid+1,dr,Y));
ArrayList<Pair> v=new ArrayList<>();
for(int i=st;i<=dr;++i)
if(Math.abs(Y.get(i).getX()-X.get(mid).getX())<=d)
v.add(Y.get(i));
for(int i=0;i<v.size()-7;++i)
for(int j=i+1;j<=i+7;++j){
int dist1=dist(v.get(i), v.get(j));
if(dist1<d) {
d=dist1;
minPair[0].setX(v.get(i).getX());
minPair[0].setY(v.get(i).getY());
minPair[1].setX(v.get(j).getX());
minPair[1].setY(v.get(j).getY());
}
}
}
return d;
}
}