能AC但是过不了样例
查看原帖
能AC但是过不了样例
591802
Sett楼主2024/9/14 15:30
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,k,x[1145141],y[1145141];
struct node
{
	int c,a;
}w[1145141];
int check(double t)
{
	int cnt=0;
	for(int i=1;i<=n;i++)
	{
		x[i]=w[i].a*w[i].c-w[i].a*t;
		y[i]=w[i].a*t-w[i].a*w[i].c;
		if(y[i]-x[i]<1e-3)cnt--;
	}
	sort(x+1,x+1+n);
	sort(y+1,y+1+n);
	int j=0;
	for(int i=1;i<=n;i++)
	{
		while(y[j+1]-x[i]<1e-4&&j<n)j++;
		cnt+=j;
	}
	if(cnt/2>=k)return 1;
	else return 0;
}
signed main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		cin>>w[i].a>>w[i].c;
	}
	double l=1,r=1009000000;
	int xx=51;
	while(xx--)
	{
		double mid=(l+r)/2.0;
		if(check(mid))
		{
			l=mid;
		}
		else r=mid;
	}
	printf("%.3f",l);
	return 0;
}
2024/9/14 15:30
加载中...