自动搬运

查看原文

来自洛谷，原作者为

	81179332_ 这个家伙很菜，什么也没有留下

搬运于2025-08-24 22:11:15，当前版本为作者最后更新于2019-10-08 10:38:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

并不会半平面交。

考虑二分答案ans,即第一名领先第二名的时间。

首先将速度的单位从$km/h$转换为$km/s$,然后我们可以处理出每跑$1$千米$n$号选手领先$i$号选手的时间为$t1_i$,每骑$1$千米$n$号选手领先$i$号选手的时间为$t2_i$($t1_i$和$t2_i$均可为负,负值表示$n$号选手落后于$i$号选手)。

对于二分的答案$ans$，对于所有的$i(1\le i<n)$要求$n$号选手领先$i$号选手不少于$ans$秒，则可以得出$n-1$个关于$k$的不等式:

只有$k$是未知数，可以对于$t1_i - t2_i$的正负分情况讨论解出k的范围:

当$t1_i - t2_i < 0$时，$k \le \frac{ans - s \times t2_i}{t1_i - t2_i}$

当$t1_i - t2_i = 0$时，$ans - s \times t2_i \le 0$若不成立，则此$ans$不合法。

当$t1_i - t2_i > 0$时，$k \ge \frac{ans - s \times t2_i}{t1_i - t2_i}$

若k有解，则此$ans$合法，否则此$ans$不合法。

题面并没有说，但是应该是在有多种方案时输出$k$最小的方案，所以最后利用二分出的答案解出$k$的范围，输出的时候用k的下界输出。

#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
int read()
{
	int x = 0;
	int f = 1;
	char ch = getchar();
	for(;!isdigit(ch);ch = getchar())
		if(ch == '-')
			f = -1;
	for(;isdigit(ch);ch = getchar())
		x = x * 10 + (ch ^ 48);
	return x * f;
}
void print(int x)
{
	if(x < 0)
		putchar('-'),x = -x;
	char ch = x % 10 + '0';
	if(x > 9)
		print(x / 10);
	putchar(ch);
}
const int N = 150;
double t1[N],t2[N],s;
int n;
bool check(double ans)
{
	double maxx = s,minn = 0;
	for(int i = 1;i < n;i++)
	{
		double l = t1[i] - t2[i],r = ans - s * t2[i];
		if(t1[i] == t2[i])
			if(r > 0)
				return false;
		if(t1[i]  > t2[i])
			minn = max(minn,r / l);
		if(t1[i] < t2[i])
			maxx = min(maxx,r / l);
	}
	return maxx > minn;
}
void P(double ans)
{
	double minn = 0;
	for(int i = 1;i < n;i++)
	{
		double l = t1[i] - t2[i],r = ans - s * t2[i];
		if(t1[i]  > t2[i])
			minn = max(minn,r / l);
	}
	printf("%.2lf %.2lf %.0lf\n",minn,s - minn,ans);
}
int main()
{
	freopen("1.in","r",stdin);
	s = read(),n = read();
	for(int i = 1;i <= n;i++)
	{
		scanf("%lf %lf",&t1[i],&t2[i]);
		t1[i] = 3600 / t1[i],t2[i] = 3600 / t2[i];
	}
	for(int i = 1;i < n;i++)
		t1[i] -= t1[n],t2[i] -= t2[n];
	double l = -1,r = 1e50;
	while(r - l >= 0.01)
	{
		double mid = (l + r) / 2;
		if(check(mid))
			l = mid;
		else
			r = mid;
	}
	if(r < 0)
		puts("NO");
	else
		P(r);
}