牛客寒训营4 D(y=k*x + b是吧)

题目 题意: 给定(x1,y1),(x0,y0).(x1,y1)在接下来的n秒，(x1,y1)会按照给出的向量(xi,yi)移动。第i秒移动(xi,yi)。在此期间，求(x1,y1)与(x0,y0)的最短距离。 思路: 要么是顶点与(x0,y0)求距离，要么是(x0,y0)到AB所在直线的距离。(要保证直线与(x0,y0)的交点在AB两点之间)。就呼呼的求个直线表达式，再算个交点坐标，再算个点到直线的距离，呼呼算。简单做麻烦了。   按std的做法，可以先判断三个点组成的三角形中，线段两端是否为钝角，如果是钝角，寄。否则交点在两点之间。根据S = 2 * AB * h，S由海伦公式 p = (a+b+c)/2,S = sqrt(p*(p-a)(p-b)(p-c))得到。 时间复杂度: O(n) 代码:

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define OldTomato ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define fir(i,a,b) for(int i=a;i bb*bb + cc*cc)
	{
		return true;
	} 
	if(bb * bb > aa*aa + cc*cc)
	{
		return true;
	} 
	return false;
}
double h(Point a,Point b,Point c)
{
	double aa = dist(b,c);
	double bb = dist(a,c);
	double cc = dist(a,b);
	double p = (aa+bb+cc)/2;
	double S = sqrt(p*(p-aa)*(p-bb)*(p-cc));
	return 2*S/cc;
}
void solve()
{
   read(n);
   for(int i=0;i