【AtCoder】ABC 348 B - Farthest Point | 茶コーダーが解くAtCoder

atcoder.jp

実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 79

問題概要

xy平面上に から までの番号が付いた 個の点がある。各点の座標は相異なり、点 の座標は である。各点について、その点からのユークリッド距離が最大である点を求めてその点の番号を出力せよ。 ただし、距離が最大である点が複数ある場合はその中で最も番号が小さい点の番号を出力すること。

制約

• 入力はすべて整数。
• 
• 

考察

個の点それぞれについて、残り 個の点とのユークリッド距離を計算してそれが最大となる点の番号を出力すればよい。全体としては2重ループの全探索になる。

ここで注意したいのが、ユークリッド距離を求める過程で平方根を取る部分である。問題文に書かれている通りにユークリッド距離を計算するとdouble型での比較が必要になるが、浮動小数点数の比較では何かと誤差が起きがちなので、可能ならば避けたいところ。

そこで今回は、「正の実数の大小関係は2乗しても変わらない」ことを利用して、ユークリッド距離の2乗の値で比較することにしている。このテクニックはAtCoderではしばしば用いるので覚えておきたい。

コード

#include <bits/stdc++.h>
using namespace std;

#define rep(i, start, end) for (ll i = (start); i < (ll)(end); i++)

// ======================================== //

int getDistance(int x1, int y1, int x2, int y2)
{
    return pow(x1 - x2, 2) + pow(y1 - y2, 2);
}

int main()
{
    int N;
    cin >> N;
    vector<int> X(N), Y(N);
    rep(i, 0, N) cin >> X[i] >> Y[i];

    rep(i, 0, N)
    {
        int max = 0;
        int max_index = 0;
        rep(j, 0, N) if (i != j)
        {
            int distance = getDistance(X[i], Y[i], X[j], Y[j]);
            if (distance > max)
            {
                max = distance;
                max_index = j;
            }
        }
        cout << max_index + 1 << endl;
    }
}

atcoder.jp

実装時間: 5分