Right Triangles [CSAcademy #68 C]

https://csacademy.com/contest/round-68/task/right-triangles/

N頂点ある。
各頂点について(x,y),(x,0),(0,0)の中に含まれる他の頂点の数を答えよ。

前提知識

• BIT

解法

条件がややこしいので言い換えよう。
頂点iの三角形の中に頂点jが含まれる為には、「y[j]/x[j]≦y[i]/x[i] かつ x[j] ≦ x[i]」を満たす必要がある。
後半の条件はそんなに難しそうではないが、前半の傾きが面倒である。
なので、三角形を処理していくが、「原点と頂点との傾きが小さい順、かつ、同じならx座標が小さい順」で点をソートして処理していこう。
この際にBITを使って、「BIT[i] := x座標がi以下の頂点数」を更新しながら数え上げよう。
このソート順でBITに点を追加しながらやっていけば、BITには今の頂点の傾き以下の傾きの頂点だけ入っていることになる。
そのため、BITを順番に更新していけば、前半の条件は必ず満たされることになる。
あとは、x[i]以下である必要があるので、BITで素早く取ってくればいい。
答えは元の点の順に戻す必要があるため、ソートする座標に頂点番号も含めておこう。

using piii = tuple<int, int, int>;
int N;
piii P[101010];
BIT<int> bit(101010);
int ans[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) {
        ll x, y; cin >> x >> y;
        P[i] = make_tuple(x, y, i);
    }
    sort(P, P + N, [&](piii a, piii b) {
        ll x, y;
        ll xx, yy;
        int i;
        tie(x, y, i) = a;
        tie(xx, yy, i) = b;

        // y / x < y' / x'
        // y * x' < y' * x
        if (y * xx == yy * x) return x < xx;
        else return y * xx < yy * x;
    });

    rep(i, 0, N) {
        int x, y, j;
        tie(x, y, j) = P[i];
        ans[j] = bit[x];
        bit.add(x, 1);
    }
    
    rep(i, 0, N) printf("%d\n", ans[i]);
}