E - 直線の傾き / Slope of a Line 解説
by 
MMNMM
点 \(p _ 1=(x _ 1,y _ 1)\) と点 \(p _ 2=(x _ 2,y _ 2)\) があり、\(x _ 1\lt x _ 2\) とします。 このとき、\(p _ 1\) と \(p _ 2\) を結ぶ線分の傾きが \(A\) 以上であることは、点 \(p _ 1\) を通る傾き \(A\) の直線 \(l _ 1\) の \(y\) 切片 \(c _ 1=y _ 1-Ax _ 1\) の値が点 \(p _ 2\) を通る傾き \(A\) の直線 \(l _ 2\) の \(y\) 切片 \(c _ 2=y _ 2-Ax _ 2\) 以下であることと同値です。
同様に、\(p _ 1\) と \(p _ 2\) を結ぶ線分の傾きが \(B\) 以下であることは、\(y _ 1-Bx _ 1\) の値が \(y _ 2-Bx _ 2\) 以上であることと同値です。
よって、求めるものは \(X _ i\lt X _ j\) かつ \(Y _ i-AX _ i\le Y _ j-AX _ j\) かつ \(Y _ i-BX _ i\ge Y _ j-BX _ j\) を満たす整数の \(2\) つ組 \((i,j)\ (1\le i\le N,1\le j\le N)\) の個数となります。
ここで、すべての点を \(Y _ i-AX _ i\) の昇順に（\(Y _ i-AX _ i\) の値が等しい \(2\) 点は \(Y _ i-BX _ i\) が大きいほうが先になるように）並べ替え、改めて点の番号を \(1,2,\ldots,N\) と振り直したとき、求めるものが \(1\le i\lt j\le N\) かつ \(Y _ i-BX _ i\ge Y _ j-BX _ j\) を満たす整数の \(2\) つ組 \((i,j)\) の個数と等しいことを示します。
証明
\(A=B\) のとき、\(Y _ i-AX _ i=k\) を満たす \(i\) が \(n _ k\) 個あるとして、答えは \(\displaystyle\sum _ {k\in\mathbb Z}\dfrac{n _ k(n _ k-1)}2\) です。 これは \(X _ i\) の大小関係によらないため、並べ替え後の番号で大小関係を制限しても正しく数え上げることができます。
\(A\lt B\) のとき、\(y _ 1-Ax _ 1\le y _ 2-Ax _ 2\) かつ \(y _ 1-Bx _ 1\ge y _ 2-Bx _ 2\) なら \((A-B)(x _ 1-x _ 2)\ge0\) が成り立つため、\(x _ 1-x _ 2\le 0\) です。 それぞれの点の \(x\) 座標は相異なるため、\(x _ 1\lt x _ 2\) が成り立ち、並べ替え後の数え上げの条件が必要十分であることがわかります。
あとは、転倒数を求めるアルゴリズムを少し変形することでこのような \((i,j)\) の個数を求めることができます。
実装例は以下のようになります。
#include <iostream>
#include <vector>
#include <algorithm>
#include <atcoder/fenwicktree>
using namespace std;
int main() {
int N, A, B;
cin >> N >> A >> B;
vector<pair<long, long>> points(N);
for (auto& [x, y] : points) {
long X, Y;
cin >> X >> Y;
x = Y - A * X; // Y-AX の昇順に
y = B * X - Y; // 同じなら Y-BX の降順に
}
ranges::sort(points);
for (int i = 0; i < N; ++i) {
points[i] = make_pair(points[i].second, i);
}
ranges::sort(points);
// 転倒数と同様のアルゴリズムで数え上げ
atcoder::fenwick_tree<long> bit(N);
long ans = 0;
for (int i = 0; i < N; ++i) {
ans += bit.sum(0, points[i].second);
bit.add(points[i].second, 1);
}
cout << ans << endl;
return 0;
}
from atcoder.fenwicktree import FenwickTree
N, A, B = map(int, input().split())
points = []
for i in range(N):
X, Y = map(int, input().split())
points.append((Y - A * X, B * X - Y))
points.sort()
points = [(p[1], i) for i, p in enumerate(points)]
points.sort()
# 転倒数と同様のアルゴリズムで数え上げ
bit = FenwickTree(N)
ans = 0
for x, y in points:
ans += bit.sum(0, y)
bit.add(y, 1)
print(ans)
投稿日時:
最終更新: