Cod sursa(job #1846835)

Utilizator Kira96Denis Mita Kira96 Data 14 ianuarie 2017 01:54:35
Problema Cele mai apropiate puncte din plan Scor 70
Compilator java Status done
Runda Arhiva educationala Marime 3.09 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;

    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, 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();
  }
}