AtCoder Beginner Contest 033 D - 三角形の分類

問題

abc033.contest.atcoder.jp

解法

各頂点 i について i 以外の頂点について偏角ソートします。

あるペア (j, k) (j < k) について, angle(j, k) == pi/2 であったら, 三角形 (i, j, k) は確実に直角三角形と言えるし, angle(j, k) > pi/2 であったら, 三角形(i, j, k) は確実に鈍角三角形であると言えます。また, 直角や鈍角になる場所はたかだか 1 つしかないので, 重複して数えることもありません。

また, cnt90 = (直角三角形の数), cnt = (鈍角三角形の数) として, 鋭角三角形は n*(n-1)*(n-2)/6 -cnt-cnt90 とすれば得られます。

というだけなんですが, 偏角ソートして angle(j, k) が pi/2 か pi/2 より大きいかとかを求めるのに手間取ってる間にコンテストが終わってしまいました。偏角を (-pi, pi) の範囲だけで考えるとかなり汚いコードになるので, 各偏角を 2*pi だけ足したものも配列に入れ, 「i-j の角度 + pi/2 の角度を持つ頂点の数」, 「i-j の角度 + pi/2 〜 i-j の角度 + pi の角度を持つ頂点の数」を求めると, かなり簡単に書けます。

const int MAXN = 2222;
ll x[MAXN], y[MAXN];

const double eps = 1e-10;
double add(double a, double b) {
    if (abs(a+b) < eps * (abs(a)+abs(b))) return 0;
    return a+b;
}

bool equal(double a, double b) {
    return add(a, -b) == 0;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N;
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> x[i] >> y[i];
    }
    ll sum = N*(N-1)*(N-2)/6;
    ll cnt90 = 0, cnt = 0;
    const double pi = acos(-1);
    for (int i = 0; i < N; i++) {
        vector<double> v;
        for (int j = 0; j < N; j++) {
            if (i==j) continue;
            v.push_back(atan2(y[j]-y[i], x[j]-x[i]));
        }
        sort(v.begin(), v.end());
        for (int j = 0; j < N-1; j++) v.push_back(v[j]+2*pi);
        for (int j = 0; j < N-1; j++) {
            cnt90 += upper_bound(v.begin(), v.end(), v[j]+pi/2+eps) - lower_bound(v.begin(), v.end(), v[j]+pi/2-eps);
            cnt += lower_bound(v.begin(), v.end(), v[j]+pi) - upper_bound(v.begin(), v.end(), v[j]+pi/2+eps);
        }
    }
    cout << sum-cnt-cnt90 << " " << cnt90 << " " << cnt << endl;
    return 0;
}