https://kyopro.hateblo.jp/entry/2019/02/06/010004

問題. 三角形の分類

平面上にどの3点も同一直線上にない $n$ 個の点が与えられる． $i \in \{1, \ldots, n\}$ 番目の点 $p_i$ の座標を $(x_i, y_i)$ とする． $n$ 個の点の中から異なる3点を選び三角形を作る．その中で鋭角三角形，直角三角形と鈍角三角形の数をそれぞれ求めよ．

制約： $3 \le n \le 2,000$

解法．角度でソート（`atan2(y, x)` 関数を使用）

鋭角三角形とは3つの角度が全て 90° よりも小さい三角形，直角三角形はちょうど1つの角度が 90° となる三角形，鈍角三角形とはちょうど1つの角度が 90° よりも大きい三角形である．また，三角形の内角の和は 180° なので 90° 以上の大きさの角は高々1つである．したがって，2辺のなす角度がちょうど 90° となるものと，90° よりも大きいものを数えることによってそれぞれ直角三角形と鈍角三角形を数えることとする．直角三角形と鈍角三角形の数が分かれば，三角形の総数が $n \choose 3$ であることから鋭角三角形の数が分かる．

任意に点 $p$ を選ぶ．ここで， $p$ 以外の異なる2点 $p_i, p_j$ で ∠ $p_i p p_j$ の大きさが 90° 以上となる $p_i, p_j$ の組合せ数を求めることを考える． $p$ が原点となるように全ての点を平行移動する．ここでは， $p$ が元から原点にあると仮定して議論を進める． $p$ 以外の点に対して，原点を端点としてその点を通る半直線と $x$ 軸の負の部分の半時計回りになす角度を考えて，その角度が小さい順に並べたものを $p'_1, p'_2, \ldots, p'_{n-1}$ とする．これは，atan2(y'_i, x'_i) 関数（atan2 - cpprefjp C++日本語リファレンス）を使用してソートすることによって $O(n \log n)$ 時間で求めることができる．下の図の番号は atan2(y'_i, x'_i) の値が何番目に小さいかを示している．ここで，10番目の点の値は $\pi$ に近い正の値となることに注意する．
　　　　　　 f:id:tatanaideyo:20190206002921p:plain:w500

$p'_1$ に対して，∠ $p'_1 \,p \,p'_{i_1}$ が 90° 以上となる最小の添字 $i_1$ と，∠ $p'_1 \, p \, p'_{j_1}$ が 180° より大きくなる最小の添字 $j_1$ を求める．どの3点も一直線上にないので，直角三角形の候補となるものは ∠ $p'_1\, p\, p'_{i_1}$ のみで，この角度が 90° でなければ $p'_1 p$ を辺とする直角三角形は存在しない．また， $p'_1 p$ を辺とする鈍角三角形の数は $j_1 - i_1$ となる．次に $p'_2$ に対して同様の条件を満たす添字 $i_2$ と $j_2$ を求めて $p'_2 p$ を辺とする直角三角形と鈍角三角形を求める．同様の計算を順番に $p'_{n-1}$ まで行う．このとき，求めた各添字は $i_1 \le i_2 \le \ldots i_{n-1}$ かつ $j_1 \le j_2 \le \ldots j_{n-1}$ を満たすので尺取り法で $O(n)$ 時間で求めることができる．実装では点の列を拡張して
　　 $p'_1, p'_2, \ldots, p'_{n-1}, p'_1 + 2 \pi, p'_2 + 2 \pi, \ldots, p'_{n-1} + 2 \pi$
として添字を計算すると簡潔に書くことができる．
以上で，任意の点 $p$ に対して，∠ $p_i p p_j$ となる直角三角形と鈍角三角形が $O(n \log n)$ 時間で求めることができたので，全体で $O(n^2 \log n)$ 時間で答えを求めることができる．

計算幾何の問題では数値誤差の対策が必要となる．この問題では円周率を double pi = acos(-1) と近似しているので，2辺のなす角度を尺取り法で調べる部分で注意が必要である．下の実装では，適当な微小量 ESP を定義しておき，a = b を abs(a - b) <= EPS として判定をしている．

計算時間： $O(n^2 \log n)$

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

const double PI = acos(-1);
constexpr double EPS = 1e-10;
struct Point { int x, y; };

int main() {
    cin.tie(0); ios::sync_with_stdio(false);

    long long n;
    cin >> n;

    vector<Point> p(n);
    for (int i = 0; i < n; ++i)
        cin >> p[i].x >> p[i].y;

    vector<long long> ans(3); // 鋭角三角形，直角三角形，鈍角三角形
    for (int i = 0; i < n; ++i) {
        vector<double> rad;
        rad.reserve(2 * n - 2);

        for (int j = 0; j < n; ++j)
            if (i != j) rad.push_back(atan2(p[j].y - p[i].y, p[j].x - p[i].x));
        sort(rad.begin(), rad.end());

        for (int j = 0; j < n; ++j)
            rad.push_back(rad[j] + 2.0 * PI);

        int first = 1, last = 1;
        for (int j = 0; j + 1 < n; ++j) {
            while (rad[first] - rad[j] < 0.5 * PI - EPS) ++first;
            while (rad[last] - rad[j] <= PI + EPS) ++last;
            // 3点が同一直線上にないので PI / 2 となる点は高々1点
            if (abs(rad[first] - rad[j] - 0.5 * PI) <= EPS) {
                ++ans[1];
                ++first;
            }
            ans[2] += last - first;
        }
    }

    ans[0] = n * (n - 1) * (n - 2) / 6 - ans[1] - ans[2];
    cout << ans[0] << ' ' << ans[1] << ' ' << ans[2] << endl;

    return 0;
}

幾何の正しい用語の使い方が分からなかったので記事を書くのに時間がかかった．
幾何の問題好きだけど ABC では少なめで悲しいな．

問題. 三角形の分類

解法．角度でソート（atan2(y, x) 関数を使用）

解法．角度でソート（`atan2(y, x)` 関数を使用）