第一份 25 分代码

第二份 AC 代码

两份代码唯一的区别就是在求斜率上

// wa 25
double getk(long long x1,long long y1,long long x2,long long y2)
	{
		if( x1 == x2 )
			return 1e17;
		return 1.0 * ( y1 - y2 ) / ( x1 - x2 );
	}

// ac 100
double getk(long long x1,long long y1,long long x2,long long y2)
	{
		if( x1 == x2 )
		{
			if( y1 >= y2 )
				return -1e17;
			return 1e17;
		}
		return 1.0 * ( y1 - y2 ) / ( x1 - x2 );
	}

但我并不知道为什么，下面是这道题我的公式：

$f_j + p_j = i \times s_j + f_i + p_i - i \times s_i$

其实我跟题解写的也差不多，只是这里 $p_i=i\times cnt[i] + q_{j-1} \ , \ s_i = cnt[i] + s_{i-1}$ ，$cnt[i]$ 表示第 $i$ 时刻到达车站的人数，我们只需要注意到 $f,p,s$ 的单增性 。

---

$\ y = f_j+p_j \ , \ k = i \ , x = s_j \ , \ b = f_i+p_i-i \times s_i$

---

但在 ac代码 的计算斜率的代码中我判断了 $y1 > y2$ 是斜率为 $-\inf$ 而不是 $+\inf$ 的情况，但实际不应该存在这样的点，因为 $s_j$ 是单增的，$f_j+p_j$ 也是单增的，不可能存在 $y1>y2$ 的情况，所以这是为什么呢？