主页
Featured image of post ACM练习——P1766 液体滴落……

ACM练习——P1766 液体滴落……

一言加载中_(:з」∠)_……

文章字数:821
预计阅读时长: 分钟

题目链接

题目分析

一道模拟题……

数据范围虽然很大,但仍可暴力O(n^2)得出……
每次遍历线段,如果Ⅰ满足滴落条件,则Ⅱ判断是否为当前能滴落到的线段的最高那一个,
遍历完后如果找到top则更新状态,找不到top == -1则输出当前$x$值……

个人代码

//P1766 [液体滴落](https://www.luogu.com.cn/problem/P1766)
#include <bits/stdc++.h>

#define MAX 100005

#define high_MAX (10e9 + 5)
using namespace std;
struct typeSegment
{
    long long stX, stY, edX, edY;
    double k, b;
    void init()
    {
        long long tmp;
        k = 1.0 * (edY - stY) / (edX - stX);
        b = stY - k * stX;
        if (stX > edX) //(WA. 1)这里需注意在init中需对stX和edX进行判断,如果stX大则要swap,否则在checkInside会出错。
            tmp = stX, stX = edX, edX = tmp, tmp = stY, stY = edY, edY = tmp;
    }

    bool checkInside(int x) //Ⅰ——判断是否满足滴落条件。
    {
        return (stX < x && x < edX);
    }

    double hDrop(int x) //利用直线的解析式,即k和b来计算落到当前线段会落到哪(哪个y值)。
    {
        return k * x + b;
    }

    void dropTo(long long *x, long long *y) //更新状态
    {
        if (stY > edY)
            *x = edX, *y = edY;
        else
            *x = stX, *y = stY;
    }
} segment[MAX];
int main()
{
    long long n, xNow;
    scanf("%lld%lld", &n, &xNow);
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld%lld%lld%lld", &segment[i].stX, &segment[i].stY, &segment[i].edX, &segment[i].edY);
        segment[i].init();
    }

    long long hNow = high_MAX; //刚开始令为从无穷高处掉落。
    while (1)
    {
        double hUp = -high_MAX, hDrop; //需要用个hUp,来存能掉落到最高的线段的掉落点高度。
        long long top = -1;
        for (int i = 1; i <= n; i++)
            if (segment[i].checkInside(xNow))                                //Ⅰ——满足掉落条件。即在线段横坐标里面。
                if ((hDrop = segment[i].hDrop(xNow)) > hUp && hNow >= hDrop) //(WA. 2)第一个判断:判断这个掉点是否是最高的,因为只能掉到最高那个线段。第二个判断:掉点是否在当前高度下,注意为掉点。
                    top = i, hUp = hDrop;
        if (top != -1)
            segment[top].dropTo(&xNow, &hNow);
        else
            return printf("%lld", xNow), 0;
    }

    return 0;
}

WA记录

第一次

checkInside直接用的stX < x < edX,但会存在stX > edX的情况……
故要在init中判断这种情况并swap……

第二次

这里之前第二个判断写的为:hNow > (segment[i].edY<segment[i].stY ? segment[i].edY : segment[i].stY)……
也就是拿这条线段的最低端点判断……

但对于如下情况:

  ↓
\     /
 \   /
  \ /
   X
  / \
 /

这样的话掉落完第一条线段到右侧后,hNow确实大于第二条线段最低点,故使答案错误……