UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#143341#8. 小w、小j和小zXiao_mo036ms1268kbC++1.5kb2021-11-17 20:58:512021-11-17 20:58:52

answer

//#pragma GCC optimize("Ofast","inline","-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
//#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ll long long
#define inf 1e8
#define rg register
using namespace std;
const int N=1e5+10;
inline ll read(){
	register ll s=0,f=0;
	register char ch=getchar();
	while(!isdigit(ch)) f|=(ch=='-'),ch=getchar();
	while(isdigit(ch)) s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
	return f?-s:s;
}
inline void write(ll x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
int n,k;
struct data{
	ll p,v;
}a[N];
struct qj{
	double l,r;
}b[N];
inline bool cmp(qj a,qj b){
	if(a.r==b.r)return a.l<b.l;
	return a.r<b.r;
}
inline bool check(double x){
	for(int i=1;i<=n;i++){
		if(a[i].v>=0)b[i]={a[i].p,a[i].p+x*a[i].v};
		else b[i]={a[i].p+x*a[i].v,a[i].p};
	}
	sort(b+1,b+1+n,cmp);
//	for(int i=1;i<=n;i++){
//		printf("l=%.5lf r=%.5lf\n",b[i].l,b[i].r);
//	}
	int cnt=1;
	double ls=b[1].r;
	for(int i=2;i<=n;i++){
		if(ls<b[i].l)cnt++,ls=b[i].r;
	}
//	printf("x=%.5lf ",x);
//	printf("%d\n",cnt);
	if(n-cnt<=k)return 1;
	return 0;
}
int main() {
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	n=read(),k=read();
	for(int i=1;i<=n;i++)a[i].p=read(),a[i].v=read();
	double l=0,r=2e9,ans;
	while(r-l>=0.000000001){
		double mid=(l+r)/2;
		if(check(mid))ans=mid,l=mid;
		else r=mid;
	}
	if(ans>=2e9-0.000001)printf("Forever");
	else printf("%.4lf",ans);
	return 0;
}

Details

小提示:点击横条可展开更详细的信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 1204kb

input:

20 10
-715624307 -28629151
957936621 17210368
-753657459 59049
-40974960 5153632
-402454312 -3450252...

output:

3.3174

result:

wrong answer expected 11.3999000000, found 3.3174000000

Subtask #2:

score: 0
Wrong Answer

Test #6:

score: 0
Wrong Answer
time: 0ms
memory: 1212kb

input:

200 10
-487405787 3200000
725249085 28629151
-671026855 -4084101
38046635 45435424
-188495128 643634...

output:

0.0028

result:

wrong answer expected 0.0039000000, found 0.0028000000

Subtask #3:

score: 0
Skipped

Subtask #4:

score: 0
Wrong Answer

Test #18:

score: 15
Accepted
time: 9ms
memory: 1268kb

input:

2000 10
882856800 -387420489
866607093 -134217728
481381898 1
-488180557 1953125
-783185249 -19683
-...

output:

0.0002

result:

ok answer is 0.0001000000

Test #19:

score: 0
Accepted
time: 14ms
memory: 1268kb

input:

2000 10
882856800 -177147
866607093 -48828125
481381898 1
-488180557 48828125
-783185249 -362797056
...

output:

0.0001

result:

ok answer is 0.0001000000

Test #20:

score: -15
Wrong Answer
time: 13ms
memory: 1264kb

input:

2000 10
882856800 -1
866607093 -396
481381898 21
-488180557 6
-783185249 -10
-816111307 -33761
99248...

output:

2.6194

result:

wrong answer expected 2.6237000000, found 2.6194000000

Subtask #5:

score: 0
Skipped

Subtask #6:

score: 0
Skipped