Cod sursa(job #1846834)

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


public class Main {
  static class Point implements Comparable{
    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;
    }

    @Override
    public int compareTo(Object val) {
      Point baseVal = (Point)val;
      return x.compareTo(baseVal.x);
    }

  }

  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;

    ArrayList<Point> aux = new ArrayList<Point>();
    ArrayList<Point> aux2 = new ArrayList<Point>();

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

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

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

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

    int t = 0;

    for (int i = left; i <= right; i += 1) {
      points[i] = aux2.get(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);

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