ABC 225 E - 7 (排序+思维)

链接

题意：

给出你n个点，然后他会与构成然后让你连接与这两个个点，其区间内不会有其他点介入，就算合格。我们可以删除一些点，问最多有多少个合格的。

分析：

题意证不太明白的话手模下样例就好了。

可以看到我们对于中有一个蓝线不合法，对于中也有一个蓝线不合法，所以我们可以将删除，这样就有两个合法的点了。

所以我们只需要知道一个点两端的斜率，然后对其进行排序使其没有重合的就好了，注意会卡double，我们选择用long double

// Problem: E - 7
// Contest: AtCoder - UNICORN Programming Contest 2021(AtCoder Beginner Contest 225)
// URL: https://atcoder.jp/contests/abc225/tasks/abc225_e
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

/// 欲戴皇冠，必承其重。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef unsigned long long ull;

#define x first
#define y second
#define sf scanf
#define pf printf
#define PI acos(-1)
#define inf 0x3f3f3f3f
#define lowbit(x) ((-x)&x)
#define mem(a,x) memset(a,x,sizeof(a))
#define rep(i,n) for(int i=0;i<(n);++i)
#define repi(i,a,b) for(int i=int(a);i<=(b);++i)
#define repr(i,b,a) for(int i=int(b);i>=(a);--i)
#define debug(x) cout << #x <<": " << x << endl;

const int MOD = 998244353;
const int mod = 998244353;
const int N = 3e5 + 10;
const int dx[] = {0, 1, -1, 0, 0};
const int dy[] = {0, 0, 0, 1, -1};
const int dz[] = {1, -1, 0, 0, 0, 0 };
int day[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

ll n, m;
string str;
struct node {
long double l,r;
}q[N];
bool cmp(node a,node b){
return a.r<b.r;
}
void solve()
{
cin>>n;
long double x,y;
for(int i = 1;i<=n;i++){
cin>>x>>y;
q[i].l=(y-1)*1.0/x;
if(x>1){
q[i].r=y*1.0/(x-1);
}else {
q[i].r=1e9+10;
}
}
sort(q+1,q+1+n,cmp);
long double r=-1e9;
ll ans=0;
for(int i=1;i<=n;i++){
if(q[i].l>=r){
ans++;
r=max(q[i].r,r);
}
}
cout<<ans<<endl;


}
int main()
{
ll t = 1;
//scanf("%lld", &t);
while(t--)
{
solve();
}
return 0;
}