P4642

P4642 [BJWC2008] 方程

(题目描述不如原题清晰)

... ... ...

AC代码

const int N = 100005;
const f80 eps = 1e-10;
const f64 INF_MARK = -1e18; // 使用一个极小值作为无解标记

struct Line { i64 a, b, c; int id; } l[N], q[10005];
typedef pair<f80, f80> Point;
Point p[N];
int stk[N];
f64 ans[10005];

inline bool cmp(const Line &x, const Line &y) {
    i64 tmp = x.a * y.b - x.b * y.a;
    if (tmp != 0) return tmp > 0;
    return (x.c * y.b - x.b * y.c) > 0;
}

inline Point Intersect(const Line &x, const Line &y) {
    i64 d = x.a * y.b - x.b * y.a;
    f80 px = (f80)x.c * y.b - (f80)x.b * y.c;
    f80 py = (f80)x.a * y.c - (f80)x.c * y.a;
    return make_pair(px / d, py / d);
}

inline bool PointOnLine(const Line &pl, const Point &pp) {
    return (pl.a * pp.first + pl.b * pp.second - pl.c) > -eps;
}

int main() {
    init();
    int n, m;
    read(n); read(m);
    for (int i = 1; i <= n; ++i) {
        read(l[i].a); read(l[i].b); read(l[i].c);
    }
    sort(l + 1, l + n + 1, cmp);
    int siz = 1;
    for (int i = 2; i <= n; ++i) {
        if (l[i].a * l[i - 1].b == l[i - 1].a * l[i].b) continue;
        l[++siz] = l[i];
    }
    
    if (siz == 1) {
        while (m--) {
            int S, T;
            read(S); read(T);
            if ((i64)S * l[1].b != (i64)T * l[1].a) write("IMPOSSIBLE\n");
            else {
                char buff[32];
                sprintf(buff, "%.5f\n", (double)((f80)l[1].c * S / l[1].a));
                write(buff);
            }
        }
        return 0;
    }

    int tp = 2;
    stk[1] = 1; stk[2] = 2;
    p[1] = {0, (f80)l[1].c / l[1].b};
    p[2] = Intersect(l[1], l[2]);

    for (int i = 3; i <= siz; ++i) {
        while (tp > 1) {
            if (PointOnLine(l[stk[tp]], Intersect(l[i], l[stk[tp-1]]))) --tp;
            else break;
        }
        p[tp + 1] = Intersect(l[i], l[stk[tp]]);
        stk[++tp] = i;
    }

    for (int i = 1; i <= m; ++i) {
        read(q[i].a); read(q[i].b); q[i].id = i;
        ans[i] = INF_MARK; 
    }
    sort(q + 1, q + m + 1, cmp);

    int cur = 1;
    for (int i = 1; i <= m; ++i) {
        if (q[i].a * l[1].b > q[i].b * l[1].a) { 
            continue; 
        }
        int pl = stk[tp];
        if (q[i].a * l[pl].b < q[i].b * l[pl].a) break;
        while (cur <= tp) {
            pl = stk[cur];
            if (q[i].a * l[pl].b - q[i].b * l[pl].a >= 0) {
                ans[q[i].id] = q[i].a * p[cur].first + q[i].b * p[cur].second;
                break;
            }
            cur++;
        }
    }

    for (int i = 1; i <= m; ++i) {
        if (ans[i] > INF_MARK + 1.0) { 
             char buff[32];
             sprintf(buff, "%.5f\n", (double)ans[i]);
             write(buff);
        }
        else write("IMPOSSIBLE\n");
    }
    return 0;
}

解决思路参考洛谷题解，注意到根据对偶可化作半平面交求解，否则TLE。