AOJ 3167 Many Points (HUPC 2020 day1-D)

面白かった！

• 問題へのリンク
• editorial

問題概要

次の問題が ケース分与えられる。

二次元平面上に 個の格子点が与えられる。これらに対し、以下の条件を満たす直線 が存在するかどうかを判定せよ。

• どの点に対しても、 との距離が等しい

制約

• 
• 

考えたこと

まず 2 点 に対して、直線 がそれらとの距離が等しくなる条件を求める。それは以下のいずれかを満たすことである:

• 直線 と平行である
• 線分 の中点を通る

これを踏まえて、次に 3 点 について考える。ここでは簡単のため、 が同一直線上にはなく、三角形を形成するとする。このとき少し考えると

• 辺 AB の中点と、辺 BC の中点を通る直線
• 辺 BC の中点と、辺 CA の中点を通る直線
• 辺 CA の中点と、辺 AB の中点を通る直線

の 3 個しかないことがわかる。

今回の問題へ

まず のケースは Yes である。

そして、 点が同一直線上にある場合はコーナーケースであり、その場合は Yes となる。

そうでない場合は 点のうちの 3 点であって三角形をなすものが存在するので、それらのうちの 2 辺の中点を通る直線 3 本に候補が絞られる。その 3 本を試せば良い。そのテストは次のように行える。

• 三角形 ABC の辺 AB と辺 AC の中点を通る直線を考えているとする
• すべての点 X に対して、XA と XB のいずれか一方が直線 BC と平行であれば Yes、そうでなければ No

注意点として、平行 check は整数の範囲内のみで行える。double 型を使うと誤差 WA することがある模様。計算量は となる。

コード

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

bool isheiko(long long dx1, long long dy1, long long dx2, long long dy2) {
    return dx1 * dy2 == dy1 * dx2;
}

bool solve(const vector<long long> &x, const vector<long long> &y) {
    int N = (int)x.size();
    if (N <= 3) return true;
    int k = -1;
    for (int i = 2; i < N; ++i) {
        if (!isheiko(x[i]-x[0], y[i]-y[0], x[1]-x[0], y[1]-y[0])) k = i;
    }
    if (k == -1) return true;

    vector<long long> ax = {x[0], x[1], x[k]}, ay = {y[0], y[1], y[k]};
    for (int iter = 0; iter < 3; ++iter) {
        long long dx = ax[(iter+2)%3] - ax[(iter+1)%3];
        long long dy = ay[(iter+2)%3] - ay[(iter+1)%3];
        bool ok = true;
        for (int i = 0; i < N; ++i) {
            if (!isheiko(x[i]-ax[iter], y[i]-ay[iter], dx, dy) &&
                !isheiko(x[i]-ax[(iter+1)%3], y[i]-ay[(iter+1)%3], dx, dy))
                ok = false;
        }
        if (ok) return true;
    }
    return false;
}

int main() {
    int T; cin >> T;
    while (T--) {
        int N; cin >> N;
        vector<long long> x(N), y(N);
        for (int i = 0; i < N; ++i) cin >> x[i] >> y[i];
        if (solve(x, y)) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
}