Pagini recente » Cod sursa (job #3221725) | Cod sursa (job #1311398) | Cod sursa (job #3225826) | Cod sursa (job #2817705) | Cod sursa (job #1534163)
package cmap;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
class Punct implements Comparable<Punct>{
public int x;
public int y;
Punct(){}
Punct(int x, int y){
this.x = x;
this.y = y;
}
Punct(Punct p){
this.x = p.x;
this.y = p.y;
}
@Override
public int compareTo(Punct p){
if(this.x < p.x)
return -1;
if(this.x == p.x && this.y < p.y)
return -1;
return 1;
}
@Override
public String toString(){
return "(" + x + ";" + y + ")";
}
public int compareY(Punct p){
if(this.y < p.y)
return -1;
if(this.y == p.y && this.x < p.x)
return -1;
return 1;
}
public double getDistance(Punct p){
return Math.sqrt((double)(this.x-p.x)*(double)(this.x - p.x) + (double)(this.y - p.y) * (double)(this.y - p.y));
}
public void copy(Punct p){
if(p == null){
this.x = 0;
this.y = 0;
}
this.x = p.x;
this.y = p.y;
}
}
public class Main {
static ArrayList<Punct> puncte = new ArrayList<>();
static Punct ans1 = new Punct(0,0), ans2 = new Punct(0,0);
static void read(Scanner in){
int n = in.nextInt();
for(int i = 0; i < n; ++i)
puncte.add(new Punct(in.nextInt(), in.nextInt()));
}
static double getClosestPoints(int lo, int hi){
if(hi - lo <= 2){
double dmin = Double.MAX_VALUE, d;
for(int i = lo; i <= hi; ++i){
for(int j = i+1; j <= hi; ++j){
d = puncte.get(i).getDistance(puncte.get(j));
if(d < dmin){
dmin = d;
if(dmin < ans1.getDistance(ans2)){
ans1.copy(puncte.get(i));
ans2.copy(puncte.get(j));
}
}
}
}
Punct p = new Punct(0,0);
for(int i = lo; i <= hi; ++i){
for(int j = i+1; j <= hi; ++j){
if(puncte.get(i).compareY(puncte.get(j)) > 0){
p.copy(puncte.get(i));
puncte.get(i).copy(puncte.get(j));
puncte.get(j).copy(p);
}
}
}
return dmin;
}
int mid = (lo+hi)/2;
double d1 = getClosestPoints(lo, mid);
double d2 = getClosestPoints(mid+1, hi);
double d = Math.min(d1, d2);
int centru = puncte.get(mid).x;
//au venit sortate, trebuie interclasate
ArrayList<Punct> sortate = new ArrayList<>();
for(int i = lo, j = mid + 1; j <= hi || i <= lo;){
if(j > hi ||(i <= lo && puncte.get(i).compareY(puncte.get(j)) < 0)){
sortate.add(puncte.get(i++));
}
else
sortate.add(puncte.get(j++));
}
ArrayList<Punct> inBanda = new ArrayList<>();
for(Punct p : sortate){
if(p.x >= centru - d && p.x <= centru + d)
inBanda.add(p);
}
int puncteInBanda = inBanda.size();
for(int i = 0; i < puncteInBanda; ++i){
for(int j = i+1; j < puncteInBanda && j < i+7 && inBanda.get(j).y < inBanda.get(i).y + d; ++j){
d1 = inBanda.get(j).getDistance(inBanda.get(i));
if(d1 < d){
d = d1;
if(d < ans1.getDistance(ans2)){
ans1.copy(inBanda.get(i));
ans2.copy(inBanda.get(j));
}
}
}
}
return d;
}
public static void main(String[] args) throws FileNotFoundException{
File inputFile = new File("cmap.in");
File outputFile = new File("cmap.out");
Scanner input = new Scanner(inputFile);
read(input);
input.close();
if(puncte.size() > 1){
ans1.copy(puncte.get(0));
ans2.copy(puncte.get(1));
}
Collections.sort(puncte);
PrintWriter out = new PrintWriter(outputFile);
out.println(getClosestPoints(0, puncte.size()-1));
out.close();
}
}