题解 P1766 【液体滴落】

· · 题解

考前来一波题解，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;
}