昨天看题的时候理解错了hhh以为是要删掉所有相连的部分
其实是删除一些7来看见最多的7
显然每个7的左上正切值最大 右下的最小
把所有的7按照其正切值大小排序 若右下正切值大于上个选取的点的左上正切值,则不会发生遮挡,答案+1 并更新选取的点
从小正切值开始选择 可以避免少计数 很有趣的思路
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
// p/q
struct fraction{
ll p,q;
fraction(ll P = 0, ll Q = 1): p(P), q(Q){}
bool operator<(const fraction &other)const{
return p*other.q < other.p*q;
}
bool operator<=(const fraction &other)const{
return p*other.q <= other.p*q;
}
};
int main(){
int N; cin >> N;
vector<ll> x(N),y(N);
for(int i=0; i<N; i++) cin >> x[i] >> y[i];
vector<pair<fraction,fraction>> data(N);
for(int i=0; i<N; i++) data[i] = make_pair(fraction(y[i],x[i]-1),fraction(y[i]-1,x[i]));
sort(data.begin(),data.end());
int ans = 0;
fraction now;
for(auto p: data){
if(now <= p.second){
ans++;
now = p.first;
}
}
cout << ans << endl;
}