题解 P1766 【液体滴落】

ModestCoder_ · 2019-08-19 21:29:05 · 题解

一道比较烦的模拟题

首先求出每条线的解析式

发现本题支持O(n^2)做法，直接上模拟

每次枚举每条线，把横坐标代入，找到当前水滴掉落可以落到的最高的线上

然后让水滴滚到线两端较低的那端，重复此操作就行了

Code：

#include <bits/stdc++.h>
#define maxn 10010
#define LL long long
using namespace std;
struct data{
    LL x1, y1, x2, y2;
}a[maxn];
double k[maxn], b[maxn];
LL n, s;

inline int read(){
    int s = 0, w = 1;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
    for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
    return s * w;
}

int main(){
    n = read(), s = read();
    for (int i = 1; i <= n; ++i){
        a[i] = (data){read(), read(), read(), read()};
        k[i] = 1.0 * (a[i].y2- a[i].y1) / (a[i].x2 - a[i].x1);
        b[i] = 1.0 * a[i].y1 - k[i] * a[i].x1;
    }
    double hei = 1e9;
    while (1){
        double H = -1e9;
        int node = -1;
        for (int i = 1; i <= n; ++i){
            if (s <= min(a[i].x1, a[i].x2) || s >= max(a[i].x1, a[i].x2)) continue;
            double h = k[i] * s + b[i];
            if (hei <= h) continue;
            if (h > H) H = h, node = i;
        }
        if (node == -1) return printf("%d\n", s), 0;
        if (a[node].y1 > a[node].y2) hei = a[node].y2, s = a[node].x2; else
        hei = a[node].y1, s = a[node].x1;
    }
    return 0;
}