POJ 3689

3689.cpp

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cassert>
#include <algorithm>
using namespace std;

#define EPS 1e-8
#define INF 1e10

// ax + by + c = 0;
typedef struct Line {
    int a;
    int b;
    int c;
} Line;

typedef pair<double, double> Coor;

int n;
int m;
int cnt;
Line linf;
Line rinf;
Line lines[100002];
Line border[100002];
Coor ps[100002];
double ans;

// sort by slope and y-intercept
bool cmp(const Line &p, const Line &q) {
    int pt = q.a*p.b;
    int qt = p.a*q.b;

    if (pt != qt) return pt < qt;
    return q.c*p.b > p.c*q.b;
}

// get common points
inline Coor common(Line p, Line q) { 
    double x, y;

    if (q.a*p.b == p.a*q.b) return Coor(INF, INF);
    x = (p.c*q.b-q.c*p.b)/(double)(q.a*p.b-p.a*q.b);
    y = (p.c*q.a-q.c*p.a)/(double)(p.a*q.b-q.a*p.b);
    return Coor(x, y);
}

int main() {

    scanf("%d %d", &n, &m);

    for (int i=0; i<n; i++) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        lines[i].a = a;
        lines[i].b = b;
        lines[i].c = -c;
    }

    sort(lines, lines+n, cmp);
    cnt = 0;
    for (int i=0; i<n; i++) { // update border like hull convex  
        while (cnt > 1 && common(lines[i], border[cnt-2]).second + EPS > common(border[cnt-1], border[cnt-2]).second) cnt--;
        if (cnt < 1 || common(border[cnt-1], lines[i]).first < INF) border[cnt++] = lines[i];
    }

    linf = border[0]; // think of lim x -> -INF
    rinf = border[cnt-1]; // think of lim x -> INF
    --cnt; // count for ps
    for (int i=0; i<cnt; i++) {
        ps[i] = common(border[i], border[i+1]);
    }

    for (int i=0; i<m; i++) {
        int s, t;
    
        scanf("%d %d", &s, &t);
        if (linf.a*t < linf.b*s || rinf.b*s < rinf.a*t) { // if lim x -> -INF = -INF or lim x -> INF = -INF
            puts("IMPOSSIBLE");
            continue;
        }

        ans = -1.0;
        for (int j=0; j<cnt; j++) {
            double x = ps[j].first;
            double y = ps[j].second;
            double score = x*s + y*t;

            if (ans < 0.0 || ans > score+EPS) ans = score;
        }

        if (linf.a*t == linf.b*s) {
            double score = -linf.c*t/(double)linf.b;
            if (ans < 0.0 || ans > score+EPS) ans = score;
        }

        if (rinf.a*t == rinf.b*s) {
            double score = -rinf.c*t/(double)rinf.b;
            if (ans < 0.0 || ans > score+EPS) ans = score;
        }

        printf("%.5f\n", ans);
    }
}