Pagini recente » Cod sursa (job #1366335) | Monitorul de evaluare | Cod sursa (job #1244373) | Cod sursa (job #1009860) | Cod sursa (job #1825973)
package closestpair;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Scanner;
class byX implements Comparator<Point>{
@Override
public int compare(Point o1, Point o2){
return ( o1.getx() == o2.getx() )?0:( ( o1.getx() > o2.getx() )?1:-1 );
}
}
class byY implements Comparator<Point>{
@Override
public int compare(Point o1, Point o2){
return ( o1.gety() == o2.gety() )?0:( ( o1.gety() > o2.gety() )?1:-1 );
}
}
class Point{
private Integer id;
private double x;
private double y;
public Point(){
x=0;
y=0;
}
public Point( Point other ){
x = other.getx();
y = other.gety();
id = other.getid();
}
public Point(double x1,double y1, Integer i){
x = x1;
y = y1;
id = i;
}
public double getx(){
return x;
}
public double gety(){
return y;
}
public Integer getid(){
return id;
}
public double dist( Point other ){
return Math.sqrt( (x-other.getx())*(x-other.getx()) + (y-other.gety())*(y-other.gety() ) );
}
@Override
public String toString(){
return id + ": (" + x + ", " + y + ")";
}
}
class Segment{
private Point p1;
private Point p2;
private double dist;
public Segment(Point o1, Point o2){
p1 = new Point(o1);
p2 = new Point(o2);
dist = p1.dist(p2);
}
public Segment( Segment o){
p1 = o.p1;
p2 = o.p2;
dist = o.dist;
}
public double getDist(){
return dist;
}
public Point getP1(){
return p1;
}
public Point getP2(){
return p2;
}
}
class ClosestPair {
public static Segment minDist(ArrayList<Point> P, ArrayList<Integer> Px){
if( Px.size() == 2 )
return new Segment( P.get(Px.get(0)), P.get(Px.get(1)) );
Segment s1,s2,s3;
s1 = new Segment( P.get(Px.get(0)), P.get(Px.get(1)) );
s2 = new Segment( P.get(Px.get(1)), P.get(Px.get(2)) );
s3 = new Segment( P.get(Px.get(2)), P.get(Px.get(0)) );
if(s1.getDist()>s2.getDist()){
if(s1.getDist()>s3.getDist()){
return s1;
} else {
return s3;
}
} else {
if(s2.getDist()>s3.getDist()){
return s2;
} else {
return s3;
}
}
}
public static Segment Closest1(ArrayList<Point> P){
ArrayList<Point> Ord = new ArrayList<>();
Ord = cp(P);
int i, n = Ord.size();
Collections.sort(Ord, new byX());
ArrayList<Integer> Px = new ArrayList<>(n);
for( i = 0; i < n; i ++ ){
Px.add(Ord.get(i).getid());
}
Collections.sort(Ord, new byY());
ArrayList<Integer> Py = new ArrayList<>(n);
for( i = 0; i < n; i ++ ){
Py.add(Ord.get(i).getid());
}
return Closest2(P, Px, Py);
}
public static Segment Closest2(ArrayList<Point> P, ArrayList<Integer> Px, ArrayList<Integer> Py){
if(Px.size()<=3)
return minDist(P,Px);//verificam distantele dintre elementele care apar in px
ArrayList<Integer> Qx, Qy, Rx, Ry;
Qx = new ArrayList<>();
Qy = new ArrayList<>();
Rx = new ArrayList<>();
Ry = new ArrayList<>();
int i, n = Px.size();
for( i = 0; i < n; i ++ ){
if( i < n/2 ){
Qx.add(Px.get(i));
} else {
Rx.add(Px.get(i));
}
}
for( i = 0; i < n; i ++ ){
if( P.get( Py.get(i) ).getx() < P.get( Px.get(n/2) ).getx() ){
Qy.add(Py.get(i));
} else {
Ry.add(Py.get(i));
}
}
Segment d1, d2, d;
d1 = Closest2(P, Qx, Qy);
d2 = Closest2(P, Rx, Ry);
d = d1.getDist() < d2.getDist()?d1:d2;
double mid = ( P.get( Px.get(n/2 - 1) ).getx() + P.get( Px.get(n/2) ).getx() )/2;
ArrayList<Integer> Sy = new ArrayList<>();
for( i = 0; i < n; i ++ ){
double xpos = P.get( Py.get(i) ).getx();
if( ( xpos < mid && xpos > mid - d.getDist() ) || ( xpos > mid && xpos < mid + d.getDist() ) ){
Sy.add(Py.get(i));
}
}
if(Sy.size()<2)
return d;
Segment ds = new Segment( P.get(Sy.get(0)), P.get(Sy.get(1)) );
n = Sy.size();
for( i = 0; i < n; i ++ ){
int m = Math.min(i+15, n-1);
Segment dtemp;
if(i + 2 == n){
dtemp = new Segment( P.get(Sy.get(i)), P.get(Sy.get(i+1)) );
if(dtemp.getDist() < ds.getDist())
ds = new Segment(dtemp);
break;
}
int j;
for( j = i+1; j <= m; j ++ ){
dtemp = new Segment( P.get(Sy.get(i)), P.get(Sy.get(j)) );
if(dtemp.getDist() < ds.getDist())
ds = new Segment(dtemp);
}
}
if(d.getDist() < ds.getDist())
return d;
else
return ds;
}
public static ArrayList<Point> cp(ArrayList<Point> O){
ArrayList<Point> N = new ArrayList<>();
int i, n = O.size();
for( i = 0; i < n; i ++ ){
Point pt = new Point(O.get(i));
N.add(pt);
}
return N;
}
public static void main(String[] args) throws FileNotFoundException{
ArrayList<Point> Points = new ArrayList<>();
Scanner fsc = new Scanner(new File("cmap.in"));
int i, n;
n = fsc.nextInt();
for( i = 0; i < n; i ++ ){
Point pt = new Point(fsc.nextInt(),fsc.nextInt(),i);
Points.add(pt);
}
Segment result = new Segment(Closest1(Points));
PrintWriter pwf = new PrintWriter("cmap.out");
pwf.print(result.getDist());
pwf.close();
}
}