Delaunay

Main.java

import java.util.*;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Map;
import java.util.TreeMap;

public class Main {
	static class MEdge {
		int x, y;
		long v;

		public MEdge(int a, int b, long c) {
			x = a;
			y = b;
			v = c;
		}
	}

	static int[] parent = new int[65536], weight = new int[65536];

	static void init(int n) {
		for (int i = 0; i <= n; i++) {
			parent[i] = i;
			weight[i] = 1;
		}
	}

	static int findp(int x) {
		return x == parent[x] ? x : (parent[x] = findp(parent[x]));
	}

	static int joint(int x, int y) {
		x = findp(x);
		y = findp(y);
		if (x == y)
			return 0;
		if (weight[x] > weight[y]) {
			weight[x] += weight[y];
			parent[y] = x;
		} else {
			weight[y] += weight[x];
			parent[x] = y;
		}
		return 1;
	}

	static public void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		while (cin.hasNext()) {
			int n = cin.nextInt();
			M tool = new M();
			for (int i = 0; i < n; i++) {
				int x = cin.nextInt();
				int y = cin.nextInt();
				APoint2D pt = new APoint2D(x, y);
				tool.addVertex(pt, i);
			}
			tool.triangulate();

			ArrayList<MEdge> E = new ArrayList<>();
			for (int i = 0; i < tool.mEdges1.size(); i++) {
				APair<Integer, Integer> e = tool.mEdges1.get(i);
				APair<APoint2D, APoint2D> f = tool.mEdges2.get(i);
				APoint2D u = f.first;
				APoint2D v = f.second;
				long cost = (u.mX - v.mX) * (u.mX - v.mX) + (u.mY - v.mY) * (u.mY - v.mY);
				E.add(new MEdge(e.first, e.second, cost));
			}

			Collections.sort(E, (x, y) -> {
				return Long.compare(x.v, y.v);
			});

			double ret = 0;
			init(n);
			for (MEdge e : E) {
				if (joint(e.x, e.y) == 1)
					ret += Math.sqrt(e.v);
			}

			System.out.printf("%.0f\n", ret);
		}
	}
}

class APoint2D implements Comparable<APoint2D> {
	long mX;
	long mY;

	APoint2D(long x, long y) {
		mX = x;
		mY = y;
	}

	long getX() {
		return mX;
	}

	long getY() {
		return mY;
	}

	@Override
	public int compareTo(APoint2D o) {
		int t = Long.compare(mX, o.mX);
		if (t != 0)
			return t;
		return Long.compare(mY, o.mY);
	}
}

class Edge {
	int id;
	EdgeNode twin;

	public Edge(int id) {
		this.id = id;
		this.twin = null;
	}

	public void setTwin(EdgeNode twin) {
		this.twin = twin;
	}
}

class EdgeNode {
	EdgeNode prev = null;
	EdgeNode next = null;
	Edge e = null;

	public EdgeNode() {

	}

	public EdgeNode(Edge e) {
		this.e = e;
	}

	public void append(EdgeNode u) {
		u.next = this.next;
		if (this.next != null)
			this.next.prev = u;
		u.prev = this;
		this.next = u;
	}

	public EdgeNode erase() {
		EdgeNode ret = this.next;
		EdgeNode pre = this.prev;
		if (pre != null)
			pre.next = ret;
		if (ret != null)
			ret.prev = pre;
		this.next = null;
		this.prev = null;
		return ret;
	}
}

class APoint3D {
	double x, y, z;

	public APoint3D(double x, double y, double z) {
		this.x = x;
		this.y = y;
		this.z = z;
	}

	public APoint3D(APoint2D p) {
		x = p.getX();
		y = p.getY();
		z = x * x + y * y;
	}

	public void subtract(APoint3D p) {
		x -= p.x;
		y -= p.y;
		z -= p.z;
	}
}

class APair<T1, T2> {
	T1 first;
	T2 second;

	public APair(T1 x, T2 y) {
		first = x;
		second = y;
	}
}

abstract class ADelaunay<T> {

	static final double eps = 1e-6;

	static int cmpZero(double v) {
		if (Math.abs(v) > eps)
			return v > 0 ? 1 : -1;
		return 0;
	}

	static double dot(APoint3D a, APoint3D b) {
		return a.x * b.x + a.y * b.y + a.z * b.z;
	}

	static double cross(APoint2D o, APoint2D a, APoint2D b) {
		return (double) (a.getX() - o.getX()) * (b.getY() - o.getY())
				- (double) (a.getY() - o.getY()) * (b.getX() - o.getX());
	}

	static APoint3D cross(APoint3D a, APoint3D b) {
		return new APoint3D(a.y * b.z - a.z * b.y, -a.x * b.z + a.z * b.x, a.x * b.y - a.y * b.x);
	}

	static double distance(APoint2D a, APoint2D b) {
		return Math.hypot(a.getX() - b.getX(), a.getY() - b.getY());
	}

	static boolean intersection(APoint2D a, APoint2D b, APoint2D c, APoint2D d) {
		return cmpZero(cross(a, c, b)) * cmpZero(cross(a, b, d)) > 0
				&& cmpZero(cross(c, a, d)) * cmpZero(cross(c, d, b)) > 0;
	}

	static int inCircle(APoint2D a, APoint2D b, APoint2D c, APoint2D p) {
		if (cross(a, b, c) < 0) {
			APoint2D tmp = b;
			b = c;
			c = tmp;
		}
		APoint3D a3 = new APoint3D(a);
		APoint3D b3 = new APoint3D(b);
		APoint3D c3 = new APoint3D(c);
		APoint3D p3 = new APoint3D(p);
		b3.subtract(a3);
		c3.subtract(a3);
		p3.subtract(a3);
		APoint3D f = cross(b3, c3);
		// check same direction, in: < 0, on: = 0, out: > 0
		return cmpZero(dot(p3, f));
	}

	protected class Site implements Comparable<Site> {
		protected APoint2D mPoint;
		protected T mObject;

		protected Site(APoint2D p, T obj) {
			mPoint = p;
			mObject = obj;
		}

		protected T object() {
			return mObject;
		}

		protected APoint2D loc() {
			return mPoint;
		}

		@Override
		public int compareTo(ADelaunay<T>.Site other) {
			if (other == null)
				return -1;
			int t = Long.compare(loc().mX, other.loc().mX);
			if (t != 0)
				return t;
			return Long.compare(loc().mY, other.loc().mY);
		}
	}

	public abstract void outputEdge(T obj0, T obj1, APoint2D p0, APoint2D p1);

	public abstract void addVertex(APoint2D p, T obj);

	protected ArrayList<Site> mSites = new ArrayList<>();
	public ArrayList<Site> mActiveSites = new ArrayList<>();
	protected APoint2D[] mPt;
	protected int mV;
	protected EdgeNode[] mHead;

	public void addSite(APoint2D p, T obj) {
		mSites.add(new Site(p, obj));
	}

	private void prepare() {
		TreeMap<APoint2D, Site> mMap = new TreeMap<>();

		for (Site s : mSites) {
			APoint2D loc = s.loc();
			if (!mMap.containsKey(loc))
				mMap.put(loc, s);
		}

		mActiveSites.clear();
		for (Map.Entry<APoint2D, Site> e : mMap.entrySet())
			mActiveSites.add(e.getValue());

		Collections.sort(mActiveSites);

		mV = mActiveSites.size();
		mPt = new APoint2D[mV];
		for (int i = 0; i < mV; i++)
			mPt[i] = mActiveSites.get(i).loc();
		mHead = new EdgeNode[mV];
		for (int i = 0; i < mV; i++)
			mHead[i] = new EdgeNode();
	}

	private void addEdge(int u, int v) {
		Edge eu = new Edge(u);
		Edge ev = new Edge(v);
		EdgeNode nu = new EdgeNode(ev);
		EdgeNode nv = new EdgeNode(eu);
		mHead[u].append(nu);
		mHead[v].append(nv);
		ev.setTwin(nv);
		eu.setTwin(nu);
	}

	private void divide(int l, int r) {
		if (r - l <= 2) {
			for (int i = l; i <= r; i++) {
				for (int j = i + 1; j <= r; j++)
					addEdge(i, j);
			}
			return;
		}

		int mid = (l + r) / 2;
		divide(l, mid);
		divide(mid + 1, r);

		int nowl = l;
		int nowr = r;
		for (boolean update = true; update;) {
			update = false;
			APoint2D ptL = mPt[nowl];
			APoint2D ptR = mPt[nowr];
			for (EdgeNode it = mHead[nowl].next; it != null; it = it.next) {
				APoint2D t = mPt[it.e.id];
				double v = cross(ptR, ptL, t);
				if (cmpZero(v) > 0 || (cmpZero(v) == 0 && distance(ptR, t) < distance(ptR, ptL))) {
					nowl = it.e.id;
					update = true;
					break;
				}
			}
			if (update)
				continue;
			for (EdgeNode it = mHead[nowr].next; it != null; it = it.next) {
				APoint2D t = mPt[it.e.id];
				double v = cross(ptL, ptR, t);
				if (cmpZero(v) < 0 || (cmpZero(v) == 0 && distance(ptL, t) < distance(ptR, ptL))) {
					nowr = it.e.id;
					update = true;
					break;
				}
			}
		}

		addEdge(nowl, nowr); // add tangent

		for (;;) {
			APoint2D ptL = mPt[nowl];
			APoint2D ptR = mPt[nowr];
			int ch = -1;
			int side = 0;
			for (EdgeNode it = mHead[nowl].next; it != null; it = it.next) {
				if (cmpZero(cross(ptL, ptR, mPt[it.e.id])) > 0
						&& (ch == -1 || inCircle(ptL, ptR, mPt[ch], mPt[it.e.id]) < 0)) {
					ch = it.e.id;
					side = -1;
				}
			}
			for (EdgeNode it = mHead[nowr].next; it != null; it = it.next) {
				if (cmpZero(cross(ptR, mPt[it.e.id], ptL)) > 0
						&& (ch == -1 || inCircle(ptL, ptR, mPt[ch], mPt[it.e.id]) < 0)) {
					ch = it.e.id;
					side = 1;
				}
			}

			// upper common tangent
			if (ch == -1)
				break;

			if (side == -1) {
				for (EdgeNode it = mHead[nowl].next; it != null;) {
					if (intersection(ptL, mPt[it.e.id], ptR, mPt[ch])) {
						it.e.twin.erase();
						it = it.erase();
					} else {
						it = it.next;
					}
				}
				nowl = ch;
				addEdge(nowl, nowr);
			} else {
				for (EdgeNode it = mHead[nowr].next; it != null;) {
					if (intersection(ptR, mPt[it.e.id], ptL, mPt[ch])) {
						it.e.twin.erase();
						it = it.erase();
					} else {
						it = it.next;
					}
				}
				nowr = ch;
				addEdge(nowl, nowr);
			}
		}
	}

	public void triangulate() {
		prepare();
		divide(0, mV - 1);
		outputEdges();
	}

	private void outputEdges() {
		for (int u = 0; u < mV; u++) {
			for (EdgeNode it = mHead[u].next; it != null; it = it.next) {
				int v = it.e.id;
				if (v < u)
					continue;
				T uObj = mActiveSites.get(u).object();
				APoint2D uLoc = mActiveSites.get(u).loc();
				T vObj = mActiveSites.get(v).object();
				APoint2D vLoc = mActiveSites.get(v).loc();
				outputEdge(uObj, vObj, uLoc, vLoc);
			}
		}
	}
}

class M extends ADelaunay<Integer> {
	ArrayList<APair<Integer, Integer>> mEdges1 = new ArrayList<>();
	ArrayList<APair<APoint2D, APoint2D>> mEdges2 = new ArrayList<>();

	@Override
	public void outputEdge(Integer obj0, Integer obj1, APoint2D p0, APoint2D p1) {
		mEdges1.add(new APair<>(obj0, obj1));
		mEdges2.add(new APair<>(p0, p1));
	}

	@Override
	public void addVertex(APoint2D p, Integer obj) {
		this.addSite(p, obj);
	}
}