AtCoder Regular Contest #004 A : 2点間距離の最大値 ( The longest distance )
問題概要
最遠点対。
解法
O(N^2)で全探索間に合う。ちなみに凸包作ってキャリパー法でO(N*log N)。
acceptされたコード
import std.stdio, std.math, std.algorithm, std.conv, std.string; void main(){ int n = to!int(readln.chomp); auto xs = new double[0], ys = new double[0]; foreach(_; 0..n){ auto ts = readln.chomp.split; xs ~= to!double(ts[0]); ys ~= to!double(ts[1]); } double ans = 0.0; foreach(i; 0..n){ foreach(j; i+1..n){ ans = max(ans, sqrt((xs[i]-xs[j])^^2 + (ys[i]-ys[j])^^2)); } } writefln("%.13f", ans); }