题目链接
P1766 液体滴落
题目分析
一道模拟题……
数据范围虽然很大,但仍可暴力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确实大于第二条线段最低点,故使答案错误……