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

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

链接

题意：

分析：

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

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

// Problem: E - 7// Contest: AtCoder - UNICORN Programming Contest 2021(AtCoder Beginner Contest 225)// URL: Memory Limit: 1024 MB// Time Limit: 2000 ms// // Powered by CP Editor (欲戴皇冠，必承其重。#include using namespace std;typedef long long ll;typedef pair 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>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<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。