P3743 Kotori's equipment

Background

kotori Yes  nn  Devices that can be used at the same time .

Title Description

The first  i  Devices consume per second  ai​  Unit energy . The use of energy is continuous , In other words, energy is not suddenly consumed at some time , But consume at a constant speed . in other words , For any real number , stay  k  The energy consumed in seconds is  k*ai​  Company . At the beginning  i  It is stored in a device  bi​  Unit energy .

meanwhile kotori There is also a power bank that can charge any device , It can charge the connected equipment every second  p  A unit of , Charging is also continuous , I won't repeat . You can charge any device at any time , The time to switch from one device to another is ignored .

kotori Want to use these devices together , Until the energy of some equipment is reduced to  0. therefore kotori Want to know , Under the action of charger , How long can she use these devices together at most .

Input format

The first line gives two integers  n,pn,p.

Next  nn  That's ok , Each line represents a device , Give two integers , It's the equipment ai​  and  bi​.

Output format

If kotori Unlimited access to these devices , Output  -1.

Otherwise output kotori In one of the devices, the energy is reduced to  0  How long can I use it before .

sample input ：

2 1
2 2
2 1000

sample output ：

2.0000000000

sample input ：

1 100
1 1

sample output ：

-1 

Ideas ： The question is how long it takes to find the longest , Then it can be divided into two points or dp Think in the right direction ( In fact, it's because the title is binary ....), Let's split the answer , One at a time t. Then think about the conditions that the left range and the right range of the answer will meet . It's obvious here , If for a machine , His ai * t <= bi, So it means that t Within time , The machine does not need to be charged . On the contrary, we need to focus ai * t - bi, Then look at t Whether the power bank can meet all the machines within the time . If meet , Then the answer is mid ~ r, Otherwise, it means that in l ~ mid.

code as follows ：

#include <iostream>

using namespace std;

const int N = 100010;

int n, q;
double a[N], b[N], s;

bool cheak(double t)
{
	double p = t * q, sum = 0;
	
	for(int i = 1; i <= n; i ++ )
	if(a[i] * t > b[i]) sum += a[i] * t - b[i];
	
	return sum <= p;
}

int main()
{
	scanf("%d%d", &n, &q);
	for(int i = 1; i <= n; i ++ ) scanf("%lf%lf", &a[i], &b[i]), s += b[i];
	
	if(q >= s) printf("-1\n");
	else
	{
		double l = 0, r = 1e10;
		while(r - l > 1e-5)
		{
			double mid = (l + r) / 2;
			if(cheak(mid)) l = mid;
			else r = mid;
		}
		printf("%.10lf", r);
	}
	
	return 0;
}