Pagini recente » Cod sursa (job #2109433) | Cod sursa (job #2643570) | Cod sursa (job #3247155) | Cod sursa (job #415731) | Cod sursa (job #1821338)
import java.util.*;
import java.io.*;
public class Main {
static class Pair {
private long x,y;
public long getX() {
return x;
}
public void setX(long x) {
this.x = x;
}
public long getY() {
return y;
}
public void setY(long y) {
this.y = y;
}
public Pair() {
x=0;y=0;
}
public Pair (long s,long 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) {
if( i.getY()-j.getY()>0) return 1;
else return -1;
}
});
Collections.sort(X,new Comparator<Pair>(){
public int compare(Pair i, Pair j) {
if( i.getX()-j.getX()>0) return 1;
else return -1;
}
});
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 long dist(Pair a,Pair b)
{
return (a.getX() - b.getX()) * (a.getX() - b.getX()) + (a.getY()-b.getY())*(a.getY()-b.getY());
}
static long Di(int st,int dr,ArrayList<Pair> Y)
{
long d=Long.MAX_VALUE;
if(dr-st<0) return d;
if(dr-st+1<=3){
for(int i=st;i<dr;++i)
for(int j=i+1;j<=dr;++j){
long 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()-1;++i)
for(int j=i+1;j-i<=7&&j<v.size();++j){
long 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;
}
}