自动搬运

查看原文

来自洛谷，原作者为

	Zhou_SY JHFLS第零菜B

搬运于2025-08-24 21:28:51，当前版本为作者最后更新于2019-10-18 17:24:24，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

考前来一波题解，rp++

从学校oj上来的，就改了几行代码。。。

本题算法：模拟+解析式

本题考点在于

已知一直线上两点$(x_1,y_1),(x2,y2)$，求此直线解析式（初一及以上学历可跳过）

解：不妨设（shé）此直线解析式为

$$y=kx+b$$

代入两点坐标得

$$y_1=kx_1+b\quad(1)$$ $$y_2=kx_2+b\quad(2)$$

由$(1)$式减$(2)$式得

$$y_1-y_2=(x_1-x_2)k$$

于是

$$k=\frac{y_1-y_2}{x_1-x_2}$$

带入$(1)$式得

$$y_1=\frac{y_1-y_2}{x_1-x_2}x_1+b$$ $$∴b=y_1-\frac{y_1-y_2}{x_1-x_2}x_1$$

整理得

$$b=\frac{y_2x_1-y_1x_2}{x_1-x_2}$$ $$∴y=\frac{y_1-y_2}{x_1-x_2}x+\frac{y_2x_1-y_1x_2}{x_1-x_2} $$

话不多说上代码：

#include<bits/stdc++.h>
#define CSP 0 
#define S_and_J_score_up 0
using namespace std;
int n;
double X,Y;//水滴的坐标
double x[3][10010];
double y[3][10010];//板子的坐标
int main()
{
	scanf("%d%lf",&n,&X);
	Y=1000000010;
    //假定水滴从最高的地方落下
    for(int i=1;i<=n;i++)scanf("%lf%lf%lf%lf",&x[1][i],&y[1][i],&x[2][i],&y[2][i]);
	
	while(1)
	{
		int l=0;
		double k=-1000000010;
		for(int i=1;i<=n;i++)
		if(Y>min(y[1][i],y[2][i])&&min(x[1][i],x[2][i])<=X&&X<=max(x[1][i],x[2][i]))
		{
			double YYY=(y[1][i]-y[2][i])/(x[1][i]-x[2][i])*X+(x[1][i]*y[2][i]-x[2][i]*y[1][i])/(x[1][i]-x[2][i]);
            //将X代入上面推出来的公式，算出坐标
			if(Y<=YYY)continue;//落不到
			if(YYY>k)//更新
			{
				l=i;
				k=YYY;
			}
		}
        /*
        这里是判断能不能落到一个板子上
        如果能就找最上面（y坐标最大）的一个
        公式推导见上
        */
		if(l==0)
        /*
        一块板子也没有接到
        那就输出
        */
		{
			printf("%.0lf\n",X);
			break;
		}
		else
        /*
        不然就落在板子上
        因为板子是斜的（显而易见）
        所以水滴就滚到了最下端（y坐标最小的那端）
        */
		{
			if(y[1][l]<y[2][l])
			{
				X=x[1][l];
				Y=y[1][l];
			}
			else
			{
				X=x[2][l];
				Y=y[2][l];
			}
		}
	}
	return CSP-S_and_J_score_up;
}