Cod sursa(job #1276464)

Utilizator Simona13Simona Mihalca Simona13 Data 26 noiembrie 2014 14:15:24
Problema Cele mai apropiate puncte din plan Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 1.46 kb
//Se dau n pct in plan. Sa se determine distanta minima dintre doua puncte. (divide et impera)
import java.util.*;
import java.io.*;
class Punct
{  public double x,y;
}//Punct

class CompPunctX implements Comparator<Punct>
{
  public int compare(Punct a, Punct b)
  {if (a.x<b.x)
       return -1;
    if (a.x>b.x)
       return 1;
    return 0;
  }//compare
}//CompPunctX

class Main
{
  public static int n;
  public static Punct[] pct=new Punct[100];
  public static double dist(Punct a, Punct b)
  {
    return Math.sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
  }//dist

  public static double dist_min(int start, int stop)
  {
    if ((start+1)==stop) //daca au ramas doua puncte
      return dist(pct[start], pct[stop]);
    if (start>=stop)
      return -1;
    double d1, d;
    int mij;
    mij=(start+stop)/2;
    d=dist_min(start, mij);
    d1=dist_min(mij+1, stop);
    if (((d1<=d)&&(d1>=0))||(d<=0))
      d=d1;
    return d; //distanta minima stanga-dreapta
  }//dist_min

  public static void main(String args[]) throws FileNotFoundException
  {
    Scanner sc=new Scanner(new File("cmap.in"));
    int i;
    n=sc.nextInt();
    for (i=0; i<n; i++)
	    {
	      pct[i]=new Punct(); 
	      pct[i].x=sc.nextDouble();
	      pct[i].y=sc.nextDouble();
	    }//for i
    sc.close();
    Arrays.sort(pct, 0, n, new CompPunctX());
    BufferedWriter cmap = new BufferedWriter(new FileWriter("cmap.out"));
    cmap.println(dist_min(0,n-1));
    cmap.close();
  }//main
}//ex6