NPSC 2003 高中組 初賽 D.運河

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>

using namespace std;

const double eps = 1e-8;

bool db_eq(const double& a, const double& b){return fabs(a-b) <= eps;}
bool db_ne(const double& a, const double& b){return fabs(a-b) > eps;}
bool db_bg(const double& a, const double& b){return a-b >= -eps;}
bool db_sg(const double& a, const double& b){return a-b <=  eps;}
bool db_s(const double& a, const double& b){return a-b <=  -eps;}
bool db_b(const double& a, const double& b){return a-b >  eps;}
bool db_z(const double& a){return fabs(a) < eps;}
bool db_nz(const double& a){return fabs(a) >= eps;}
bool db_pos(const double& a){return a>= eps;}
bool db_neg(const double& a){return a<=-eps;}

struct pt{ double x, y; pt(double _x = 0, double _y = 0): x(_x), y(_y){return;}};
pt operator+(const pt& a, const pt& b){return pt(a.x+b.x, a.y+b.y);}
pt operator-(const pt& a, const pt& b){return pt(a.x-b.x, a.y-b.y);}
double operator^(const pt& a, const pt& b){return a.x*b.y - a.y*b.x;}
pt operator~(const pt& a){return pt(a.y, -a.x);}
bool operator==(const pt& a, const pt& b){return db_eq(a.x,b.x) and db_eq(a.y,b.y);}

struct line{
    double a, b, c;
    line(pt m, pt p){
        a = m.y; b = -m.x;
        c = -a*p.x - b*p.y;
        return;
    }
    double len()const{return sqrt(a*a + b*b);}
    pt m()const{return pt(a, -b);}
};

struct ch_cpx{bool operator()(const pt& a, const pt& b){return db_ne(a.x, b.x) ? db_s(a.x, b.x) : db_s(a.y, b.y);}};

vector<pt> make_ch(vector<pt>& inp){
    sort(inp.begin(), inp.end(), ch_cpx());
    auto it = unique(inp.begin(), inp.end());
    inp.resize(distance(inp.begin(), it));
    int inpsz = inp.size();
   
    vector<pt> bt(inpsz), tp(inpsz);

    int btsz = 0, tpsz = 0;
    for(int lx = 0;lx < inpsz;lx++){
        while(btsz > 1 and db_pos((bt[btsz-2] - bt[btsz-1])^(inp[lx] - bt[btsz-1])))
            btsz--;
        bt[btsz++] = inp[lx];
    }
   
    for(int lx = inpsz-1;lx >= 0;lx--){
        while(tpsz > 1 and db_pos((tp[tpsz-2] - tp[tpsz-1])^(inp[lx] - tp[tpsz-1])))
            tpsz--;
        tp[tpsz++] = inp[lx];
    }

    vector<pt> ret;
    for(int lx = 0;lx < btsz;lx++) ret.push_back(bt[lx]);
    for(int lx = 1;lx < tpsz-1;lx++) ret.push_back(tp[lx]);
   
    return ret;
}

int eval(const vector<pt>& ch, const line& l){
    int acnt = 0, bcnt = 0;
    for(int lx = 0;lx < ch.size();lx++){
        double val = l.a*ch[lx].x + l.b*ch[lx].y + l.c;
        if(db_pos(val)) acnt++;
        if(db_neg(val)) bcnt++;
    }
    if(acnt and bcnt) return 2; //err
    if(acnt) return  1;
    if(bcnt) return -1;
    return 0;
}

double cal(const vector<pt>& cha, const vector<pt>& chb, line la, line lb){
    int val_aa = eval(cha, la);
    int val_ab = eval(cha, lb);
    int val_ba = eval(chb, la);
    int val_bb = eval(chb, lb);
    if(val_aa == 2 or val_ab == 2 or val_ba == 2 or val_bb == 2) return 0;
    if(val_aa == val_ba and val_aa != 0) return 0;
    if(val_ab == val_bb and val_ab != 0) return 0;
    if(db_nz(la.m()^lb.m())) return 0;
    double k = 0;
    if(db_nz(la.a)) k = lb.a/la.a;
    if(db_nz(la.b)) k = lb.b/la.b;
    return fabs(la.c*k-lb.c)/la.len();
}

int main(){
    int m, n;
    for(;;){
        scanf("%d %d", &m, &n);
        if(n == 0 and m == 0) break;
        vector<pt> ap(m), bp(n);
        for(int lx = 0;lx < m;lx++) scanf("%lf %lf", &ap[lx].x, &ap[lx].y);
        for(int lx = 0;lx < n;lx++) scanf("%lf %lf", &bp[lx].x, &bp[lx].y);
        ap = make_ch(ap);
        bp = make_ch(bp);
        double dis = 0;
        int sza = ap.size(), szb = bp.size();
        for(int lx = 0;lx < sza;lx++){
            for(int ly = 0;ly < szb;ly++){
                line la = line(~(ap[lx]-bp[ly]),ap[lx]);
                line lb = line(~(ap[lx]-bp[ly]),bp[ly]);
                dis = max(dis, cal(ap, bp, la, lb));
            }
        }
        // p2l
        for(int lx = 0;lx < sza and sza > 1;lx++){
            for(int ly = 0;ly < szb;ly++){
                line la = line(ap[lx]-ap[(lx+1)%sza], ap[lx]);
                line lb = line(ap[lx]-ap[(lx+1)%sza], bp[ly]);
                dis = max(dis, cal(ap, bp, la, lb));
            }
        }
        // l2p
        for(int lx = 0;lx < sza;lx++){
            for(int ly = 0;ly < szb and szb > 1;ly++){
                line la = line(bp[ly]-bp[(ly+1)%szb], ap[lx]);
                line lb = line(bp[ly]-bp[(ly+1)%szb], bp[ly]);
                dis = max(dis, cal(ap, bp, la, lb));
            }
        }
        //l2l
        for(int lx = 0;lx < sza and sza > 1;lx++){
            for(int ly = 0;ly < szb and szb > 1;ly++){
                line la = line(ap[lx]-ap[(lx+1)%sza], ap[lx]);
                line lb = line(bp[ly]-bp[(ly+1)%szb], bp[ly]);
                dis = max(dis, cal(ap, bp, la, lb));
            }
        }
        if(db_z(dis)) printf("IMPOSSIBLE\n");
        else printf("%.3f\n", dis);
    }
    return 0;
}