Cod sursa(job #1846836)

Utilizator Kira96Denis Mita Kira96 Data 14 ianuarie 2017 02:02:02
Problema Cele mai apropiate puncte din plan Scor 40
Compilator java Status done
Runda Arhiva educationala Marime 3.13 kb
import java.io.*;
import java.util.*;
import java.lang.Math;

class Point {
  Double x, y;
  Point(Double x, Double y) {
    this.x = x;
    this.y = y;
  }

  void swap(Point a) {
    double x2 = x;
    double y2 = y;

    x = (double)a.x;
    y = (double)a.y;

    a.x = x2;
    a.y = y2;
  }
}

public class Main {

  public static double dist(Point a, Point b) {
    return (double)(a.x - b.x) * (a.x - b.x) + (double)(a.y - b.y) * (a.y - b.y);
  }

  static long inf = ((long)1) << 60;

  /* Demonstatia completa se afla pe pagina problemei.
     Am implementat aceasta sursa si in C++, contul meu este Kira96.
  */
  static double solve(Point[] points, int left, int right) {
    if (left == right) {
      return inf;
    }

    if (right - left == 1) {
      if (points[left].y > points[right].y) {
        points[left].swap(points[right]);
      }
      return dist(points[left], points[right]);
    }

    int mid = (left + right) / 2;
    double midX = points[mid].x;
    double sol = Math.min(solve(points, left, mid), solve(points, mid + 1, right));

    int p1 = left;
    int p2 = mid + 1;

    int t1 = -1;
    int t2 = -1;

    Point[] aux = new Point[right - left + 1];
    Point[] aux2 = new Point[right - left + 1];

    for (; p1 <= mid && p2 <= right;) {
      if (points[p1].y <= points[p2].y) {
        if (midX - points[p1].x < sol) {
          aux[++t1] = points[p1];
        }
        aux2[++t2] = points[p1++];
      } else {
        if (points[p2].x - midX < sol) {
          aux[++t1] = points[p2];
        }
        aux2[++t2] = points[p2++];
      }
    }

    for (; p1 <= mid; p1 += 1) {
      if (midX - points[p1].x < sol) {
        aux[++t1] = points[p1];
      }
      aux2[++t2] = points[p1];
    }

    for (; p2 <= right; p2 += 1) {
      if (midX - points[p2].x < sol) {
        aux[++t1] = points[p2];
      }
      aux2[++t2] = points[p2];
    }

    for (int i = 0; i < aux.length; i += 1) {
      int k = Math.min(aux.length, i + 9);
      for (int j = i + 1; j < k; j += 1) {
        sol = Math.min(sol, dist(aux[i], aux[j]));
      }
    }

    int t = 0;

    for (int i = left; i <= right; i += 1) {
      points[i] = aux2[t++];
    }

    return sol;
  }

  static final String in = "cmap.in";
  static final String out = "cmap.out";

  public static void main(String[] args) throws IOException {
     BufferedReader br = new BufferedReader(new FileReader(in));
     StringTokenizer stok;
     final int n = Integer.parseInt(br.readLine());
    Point[] points = new Point[n];

    for (int i = 0; i < n; i += 1) {
      stok = new StringTokenizer(br.readLine());
      points[i] = new Point(Double.parseDouble(stok.nextToken()), Double.parseDouble(stok.nextToken()));
    }
    br.close();

    Arrays.sort(points, new Comparator<Point>(){
        @Override
        public int compare(Point a, Point b)
        {
          if(a.x - b.x < 0)
            return -1;
          if(a.x - b.x > 0)
            return 1;
          return 0;
        }
      });

    FileOutputStream fos = new FileOutputStream(out);
    PrintWriter writer = new PrintWriter((OutputStream)fos);
    writer.write(Math.sqrt(solve(points, 0, n - 1)) + "\n");
    writer.close();
  }
}