E - フ/7 Editorial by en_translator
First of all, after removing some 7’s, if there still remain 7’s that are not wholly visible from the origin, then we can remove such 7’s as well without changing the number of 7’s that are wholly visible from the origin.
Therefore, the problem can be rephrased to as follows:
Given \(N\) number of 7’s, you may remove some of them so that all remaining 7’s are visible from the origin. Find the maximum number of remaining 7’s.
Moreover, one can regard each 7 as a open interval corresponding to the polar angles of its both endpoints, so that the problem is reworded as follows:
Given are \(N\) open intervals. The left endpoint of the \(i\)-th interval is \(f(x_i,y_i-1)\) and that of the right endpoint is \(f(x_i-1,y_i)\), where \(f(i,j)\) is a function of two real numbers \((i,j)\) that represents the polar angle of coordinate \((i,j)\).
At most how many intervals can be chosen from them, so that no two different intervals do not overlap?
This is equivalent to the famous problem called interval scheduling problem. It is very famous that the interval scheduling problem can be solved by the following greedy algorithm, which can be applied for this problem as well.
Repeat the following operations infinitely.
- Let \(R_{\max}\) be the maximum coordinate of (the right endpoint of) already chosen intervals. If there exist not yet chosen intervals with the leftmost coordinates \(R_{\max}\) or greater, then choose one with the smallest rightmost coordinate.
- Otherwise, if there are no such interval with the leftmost coordinate greater than or equal to \(R_{\max}\), then terminate the procedure.
When implementing, it is a good idea to sort \(N\) intervals in the increasing order of their rightmost coordinates. The complexity is \(O(N \log N)\).
Sample code (C++)
#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;
}
posted:
last update: