Submission #25116

---

Source Code Expand

module main;

// selective import: 以下で使うものだけを import 可能
import std.stdio : readln, writefln;
import std.typecons : Tuple;
import std.algorithm : sort, reverse;
import std.math : sqrt;
import std.conv : to;
import std.string : strip, split;
alias Tuple!(int, "x", int, "y") Point; // int の組 (x, y): 名前つきのタプル (実装は struct; 辞書順の比較がデフォルトで入っている)

void main()
{
    Point[] points;
    foreach (i; 0..readln().strip().to!int())
    {
        auto buf = readln().strip().split();
        Point p;
        p.x = buf[0].to!int();
        p.y = buf[1].to!int();
        points ~= p;
    }
    // 以下で定義された凸包を計算する関数
    auto conv_hull = convex_004A(points);
    debug
    {
        dump_points("convex hull:", conv_hull);
    }
    // 尺取り法を簡単に行えるよう、凸包を2周する。
    conv_hull ~= conv_hull;
    // ユークリッド距離の2乗
    int euclidistance(Point p0, Point p1)
    {
        return (p0.x - p1.x) ^^ 2 + (p0.y - p1.y) ^^ 2;
    }
    // 凸包の i 番目と j 番目との距離 (の2乗) を観察する。
    // それまでの最大値を max へ、現在の値を current へ、j を増やしたときの値を next へ格納しておく。
    int i, j, max, current, next;
    while (true)
    {
        try
        {
            next = euclidistance(conv_hull[i], conv_hull[j+1]);
        }
        catch // j が最大値を超えたら、つまり、2周したら
        {
            // それまでの最大値をもとに平方根を出力して終了
            writefln("%f", sqrt(cast(double)(max)));
            return;
        }
        debug { writefln("i = %d, j = %d, c = %d, n = %d, max = %d", i, j, current, next, max); }
        // 最大値を更新
        if (max < next)
        {
            max = next;
        }
        if (current <= next) // j を増やすことで距離が小さくならないなら増やす
        {
            j += 1;
            current = next;
        }
        else // そうではない場合、i を増やしてみる
        {
            i += 1;
            current = euclidistance(conv_hull[i], conv_hull[j]);
            if (max < current)
            {
                max = current;
            }
        }
    }
}

debug
{
    void dump_points(string title, Point[] points)
    {
        import std.stdio;
        writeln(title);
        foreach (p; points)
        {
            writefln("%d\t%d", p.x, p.y);
        }
        writeln();
    }
}

// 凸包を O(n log n) で求める。ソート済みなら O(n) となる。
// http://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain
Point[] convex_004A(Point[] points)
{
    sort(points);
    if (points.length <= 2)
    {
        return points;
    }
    // 凸包のうち、片側から見える頂点の列を求める関数。
    // 内部は見通せないが辺は見通せる。
    Point[] half_convex(Point[] points)
    {
        // 3点の位置関係: 時計回りか反時計回りかの判別式。
        // ベクトル OA, OB を3次元ベクトルとみたときの外積 (の z 成分)。
        long cross_prod(Point o, Point a, Point b)
        {
            return (a.x - o.x) * (b.y-o.y) - (a.y - o.y) * (b.x - o.x);
        }
        Point[] ret;
        foreach (p; points)
        {
            while (ret.length > 1 && cross_prod(ret[$-2], ret[$-1], p) <= 0)
            {
                ret.length -= 1;
            }
            ret ~= p;
        }
        return ret;
    }
    Point[] lower = half_convex(points); // 下から見える部分
    reverse(points);
    Point[] upper = half_convex(points); // 上から見える部分
    return lower[0..$-1] ~ upper[0..$-1]; // つなげる
}

Submission Info

Judge Result