\(\def \set #1#2{\{ #1 \ \vert \ #2 \}}\)
解法
問題文を翻訳すれば，区間スケジューリング問題と同じ． 区間の両端を，直線の傾きと考えればよい． 整数のペアとして，傾きを有理数で扱うと比較も整数でできる．
注意
分母が0になる場合と，既約でない分数の扱い． \(a \neq 0\) のとき，
- \(a/0\) を含む類の代表元は \(1/0\) とする．
- \(0/a\) を含む類の代表元は \(0/1\) とする．
- \(b/a\) を含む類の代表元は，\(b/a\) を約分した値とする．
今回は出てこないが，負の分数は分子にマイナスを付ける． 理由は，\(y/x < w/z\) の判定が \(yz < wx\) と出来るから． もし分母にマイナスをつけてしまうと，分母を払うときに符号が逆転して面倒．
\(0/0\) は今回は出てこない．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
struct D{
ll x,y; // y/x
D(){}
D(ll x, ll y): x(x), y(y){
if(x < 0) { x *= -1; y *= -1; }
if(x == 0 && y == 0) {}
else if(x == 0) { y = 1; }
else if(y == 0) { x = 1; }
// ll d = GCD(x,y);
// x /= d, y /= d;
}
bool compare (D a, auto op) const {
return op(y*a.x, x*a.y);
}
bool operator < (D a) const {
// y/x < a.y/a.x
// return y*a.x < x*a.y;
return compare(a, [&](ll s, ll t) { return s < t; } );
}
bool operator == (D a) const {
// return y*a.x == x*a.y;
return compare(a, [&](ll s, ll t) { return s == t; } );
}
};
int main() {
ll n;
cin >> n;
rep(i,n){
ll x,y; cin >> x >> y;
D l = D(x,y-1);
D r = D(x-1,y);
p[i] = {r,l};
}
sort(all(p));
D last = D(1,-1);
ll ans = 0;
for(auto [r,l]: p) if(last < l || last == l){
ans++;
last = r;
}
cout << ans << endl;
return 0;
}
