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