国内予選のEを

Javaの幾何ライブラリを使って解いてみた。多角形と線分の距離をもとめるというそのままの関数はなかったので自分で一から書くのに比べて、そんなには楽にならなかった。

import java.awt.geom.Line2D;
import java.awt.geom.Point2D;
import java.awt.geom.Rectangle2D;
import java.util.Scanner;

class Rect {
  Point2D ps[];
  Rectangle2D rect;

  Rect(int minx, int miny, int maxx, int maxy) {
    rect = new Rectangle2D.Double(minx, miny, maxx - minx, maxy - miny);
    ps = new Point2D[4];
    ps[0] = new Point2D.Double(minx, miny);
    ps[1] = new Point2D.Double(minx, maxy);
    ps[2] = new Point2D.Double(maxx, maxy);
    ps[3] = new Point2D.Double(maxx, miny);
  }

  double dist(int sx, int sy, int ex, int ey) {
    Line2D seq = new Line2D.Double(sx, sy, ex, ey);
    if (seq.intersects(rect))
      return 0;
    double res = Double.MAX_VALUE;
    for (Point2D p : ps) {
      res = Math.min(res, seq.ptSegDist(p));
    }
    for (int i = 0; i < ps.length; i++) {
      seq = new Line2D.Double(ps[i], ps[(i + 1) % 4]);
      res = Math.min(res, seq.ptSegDist(sx, sy));
      res = Math.min(res, seq.ptSegDist(ex, ey));
    }
    return res;
  }
}

public class E {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    while (sc.hasNext()) {
      int N = sc.nextInt();
      if (N == 0)break;
      int sx = sc.nextInt() , sy = sc.nextInt() , 
          ex = sc.nextInt() , ey = sc.nextInt();
      double hs[] = new double[N];
      double ds[] = new double[N];
      for (int i = 0; i < N ; i++) {
        Rect r = new Rect(sc.nextInt(), sc.nextInt(), sc.nextInt(), sc.nextInt());
        hs[i] = sc.nextDouble();
        ds[i] = r.dist(sx, sy, ex, ey);
      }
      double low = 0.0;
      double high = 1000.0;
      while (high - low > 1.0E-6) {
        double mid = (low + high) / 2;
        if (check(hs, ds, mid)) low = mid;
        else high = mid;
      }
      System.out.println(low);
    }
  }

  static boolean check(double[] hs, double[] ds, double r) {
    for (int i = 0; i < hs.length ; i++) {
      double h = hs[i];
      double d = ds[i];
      if (r < h) {
        //pattern(a)
        if (r >= d)return false;
      } else {
        //pattern(b)
        if ((r - h) * (r - h) + d * d < r * r)return false;
      }
    }
    return true;
  }
}