半平面交

题目： Most Distant Point from the Sea

模板备忘。

对于无限大的半平面，可以用一个非常大的矩形围出一块有限的面积。
半盘面交的题目需要小心处理平行的直线。

import java.io.*;
import java.text.DecimalFormat;
import java.util.*;

public class Main {
	public static void main(String[] argv) throws FileNotFoundException {
		InputStream inS = System.in;
		//inS = new FileInputStream("input.txt");
		Scanner in = new Scanner(inS);
		while (in.hasNextInt()) {
			(new Main()).solve(in);
		}
	}
	
	final static double EPS = 1e-8;
	
	int n;
	static class Vector {
		double x, y;
		public Vector(double a, double b) {
			this.x = a;
			this.y = b;
		}
		
		public Vector add(Vector o) {
			return new Vector(x + o.x, y + o.y);
		}
		
		public Vector substract(Vector o) {
			return new Vector(x - o.x, y - o.y);
		}
		
		double norm() {
			return Math.sqrt(x * x + y * y);
		}
		
		Vector scalar(double len) {
			double t = norm();
			return new Vector(
					x * len / t,
					y * len / t);
		}
		
		double cross(Vector o) {
			return x * o.y - y * o.x;
		}
	}

	private void solve(Scanner in) {
		n = in.nextInt();
		if (n == 0) return;
		List<Vector> ps = new ArrayList<Vector>(n);
		for (int i = 0; i < n; i++) {
			ps.add(new Vector(in.nextDouble(), in.nextDouble()));
		}
		ps.add(ps.get(0));
		double lo = 0.0, hi = 100000.0;
		for (int i = 0; i < 1000; i++) {
			double me = (lo + hi) * 0.5;
			if (check(me, ps)) lo = me;
			else hi = me;
		}
		check(lo, ps);
		System.out.println(String.format("%.8f", lo));
	}
	
	static class Segment {
		Vector a, v;
		Segment(Vector a2, Vector v2) {
			a = a2;
			v = v2;
		}
		public Segment shift(double shift) {
			Vector vt = new Vector(-v.y, v.x);
			return new Segment(a.add(vt.scalar(shift)), v);
		}
		
		boolean contains(Vector p) {
			return v.cross(p.substract(a)) >= -EPS;
		}
		public Vector intersect(Segment o) {
			double ss = this.v.cross(o.v);
			double s1 = o.v.cross(this.a.substract(o.a));
			return a.add(new Vector(v.x * s1 / ss, v.y * s1 / ss));
		}
		
		boolean parallel(Segment o) {
			return Math.abs(this.v.cross(o.v)) < EPS;
		}
	}

	private boolean check(double shift, List<Vector> ps) {
		List<Segment> segs = new ArrayList<Segment>(n);
		for (int i = 0; i < n; i++) {
			Segment t = new Segment(ps.get(i), ps.get(i + 1).substract(ps.get(i))).shift(shift);
			if (segs.isEmpty() || ! t.parallel((segs.get(segs.size() - 1)))) segs.add(t);
		}
		Deque<Segment> segq = new ArrayDeque<Segment>();
		Deque<Vector> pq = new ArrayDeque<Vector>();
		segq.addLast(segs.remove(0));
		for (Segment seg : segs) {
			while (! pq.isEmpty() && ! seg.contains(pq.getLast())) {
				pq.removeLast();
				segq.removeLast();
			}
			while (! pq.isEmpty() && ! seg.contains(pq.getFirst())) {
				pq.removeFirst();
				segq.removeFirst();
			}
			if (segq.getLast().parallel(seg)) return false;
			pq.addLast(segq.getLast().intersect(seg));
			segq.addLast(seg);
		}
		while (! pq.isEmpty() && ! segq.getFirst().contains(pq.getLast())) {
			pq.removeLast();
			segq.removeLast();
		}
		while (! pq.isEmpty() && ! segq.getLast().contains(pq.getFirst())) {
			pq.removeFirst();
			segq.removeFirst();
		}
		return pq.size() > 1;
	}

}