幾何だ！！

問題概要

$H \times W$ の長方形の紙上に $N$ 個の点がある。これらの点は互いに相異なる。

これらの点から 4 つの点 A, B, C, D を選ぶ (選ぶ順番も考慮する)。そして、点 A を中心として点 B を通る円を O1 とし、点 C を中心として点 D を通る円を O2 とする。以下の条件を満たすような選び方が何通りあるか求めよ。

O1 は長方形からはみ出さない (長方形の辺に接するのは OK)
O2 は長方形からはみ出さない (長方形の辺に接するのは OK)
O1 は O2 を内部に含む (内接するのも NG)

制約

$4 \le N \le 50$
$1 \le H, W \le 1000$

考えたこと

$N \le 50$ なので $O(N^{4})$ が間に合う。ゆえに全探索するだけ！！！！！

ただし、円の包含判定について計算誤差に気をつけながら実装する必要がある。まず、

円 O1 の半径を $R_{1}$
円 O2 の半径を $R_{2}$
円 O1, O2 の中心間の距離を $d$

としたとき、円 O1 が円 O2 を内部に含む条件は

$R_{1} - R_{2} \gt d$

と表せる。不等号に等号を含まないことに注意 (等号のときは内接する)。

さらに、円 O1 が長方形にはみ出さないための条件 (O2 も同様) は、円の中心座標を $(X, Y)$ としたとき、 $D_{1} = \min(X, W-X, Y, H-Y)$ として、

$R_{1} \le D_{1}$

と表せる。今度は不等号に等号を含むことに注意！！！

誤差

実数型の数値を比較するときは誤差に気を付けるため、EPS を用いるのが定石。たとえば

double EPS = 1e-8;

などとしておいて、不等式判定を次のようにする。

$R_{1} - R_{2} \gt d$ 　→　R1 - R2 > d + EPS
$R_{1} \le D_{1}$ 　→　R1 <= D1 + EPS

EPS の値は、時にはちゃんと考えて調整する必要がある。今回は $10^{-8}$ とかで大丈夫。

誤差を扱う別解

実数型を扱う数値誤差が怖いとき、すべてを整数型で済ませる方法もある。実際上はそれが困難な場合もあるが、今回はすべて整数型で扱うこともできる。公式解説参照

https://www.ioi-jp.org/camp/2013/2013-sp-tasks/2013-sp-day1-joi_poster-review.pdf

コード

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

const double EPS = 1e-8;
int main() {
    int N, W, H;
    cin >> N >> W >> H;
    vector<double> X(N), Y(N);
    for (int i = 0; i < N; ++i) cin >> X[i] >> Y[i];

    auto calc = [&](int i, int j) -> double {
        double res = (X[i]-X[j])*(X[i]-X[j]) + (Y[i]-Y[j])*(Y[i]-Y[j]);
        return sqrt(res);
    };

    int res = 0;
    for (int a = 0; a < N; ++a) {
        for (int b = 0; b < N; ++b) {
            for (int c = 0; c < N; ++c) {
                for (int d = 0; d < N; ++d) {
                    set<int> tmp({a, b, c, d});
                    if (tmp.size() != 4) continue;
                    double R1 = calc(a, b), R2 = calc(c, d), dis = calc(a, c);
                    double D1 = min({X[a], W-X[a], Y[a], H-Y[a]});
                    double D2 = min({X[c], W-X[c], Y[c], H-Y[c]});
                    if (R1 - R2 > dis + EPS && R1 <= D1 + EPS && R2 <= D2 + EPS) {
                        ++res;
                    }
                }
            }
        }
    }
    cout << res << endl;
}