AtCoder ABC 348 B - Farthest Point (6Q, 灰色, 200 点)

面白い探索問題

• 問題へのリンク

問題概要

座標平面上に 個の点がある。点 の座標は である。

各 に対して、点 の距離が最大であるような の値を求めよ（タイがある場合は が最小のもの）。

制約

• 
• 

考えたこと

各 に対して、別々の問題を解く。

に対して

(X[i] - X[j]) * (X[i] - X[j]) + (Y[i] - Y[j]) * (Y[i] - Y[j])

の値（2 点 間の距離の平方）を求めて、それが最大となる を求めれば良い。

コード

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

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

    for (int i = 0; i < N; i++) {
        int max_distance = 0, max_index = -1;
        for (int j = 0; j < N; j++) {
            int dist = (X[i] - X[j]) * (X[i] - X[j]) + (Y[i] - Y[j]) * (Y[i] - Y[j]);
            if (max_distance < dist) {
                max_distance = dist;
                max_index = j;
            }
        }
        cout << max_index+1 << endl;
    }
}