Cod sursa(job #1781537)

Utilizator oldatlantianSerban Cercelescu oldatlantian Data 16 octombrie 2016 22:49:03
Problema Tunelul groazei Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.02 kb
#include <bits/stdc++.h>
using namespace std;
typedef double f64;

const f64 INF = 1e14,
          EPS = 1. / INF;

struct PTX {
    f64 x, y;

    inline PTX() { }
    inline PTX(f64 _x, f64 _y) {
        x = _x;
        y = _y;
    }

    bool operator < (const PTX &arg) const {
        return (abs(x-arg.x)<EPS) ? (y < arg.y) : (x < arg.x);
    }

    bool operator == (const PTX &arg) const {
        return abs(x-arg.x)<EPS && abs(y-arg.y)<EPS;
    }
};

vector<PTX> pa, pb, res;

f64 ccw(const PTX &a, const PTX &b, const PTX &c) {
    return (a.x-b.x)*(c.y-b.y)-(a.y-b.y)*(c.x-b.x);
}

f64 take_area(vector<PTX> pol) {
    f64 area = 0.0;
    int n = pol.size();

    for(int i=0; i<n; ++i)
        area+= ccw(PTX(0.0, 0.0), pol[i], pol[(i+1)%n]);

    return abs(area) / 2.0;
}

int sgn(f64 arg) {
    if(abs(arg)<EPS)
        return 0;
    if(arg>=EPS)
        return 1;
    if(arg<=-EPS)
        return -1;
}

bool intersect(const PTX &a0, const PTX &a1, const PTX &b0, const PTX &b1) {
    if(abs(a0.x-a1.x)<EPS && abs(b0.x-b1.x)<EPS) return false;
    if(abs(a0.y-a1.y)<EPS && abs(b0.y-b1.y)<EPS) return false;

    return sgn(ccw(a0, a1, b0) * ccw(a0, a1, b1)) == -1 &&
           sgn(ccw(a1, a0, b0) * ccw(a1, a0, b1)) == -1 &&
           sgn(ccw(b0, b1, a0) * ccw(b0, b1, a1)) == -1 &&
           sgn(ccw(b1, b0, a0) * ccw(b1, b0, a1)) == -1;
}

bool inside(PTX pt, vector<PTX> pol) {
    int n = pol.size();
    f64 ra, ta; // ratatata....

    ra = 0.;
    ta = 0.;

    for(int i=0; i<n; ++i) {
        ra+= ccw(PTX(0.0, 0.0), pol[i], pol[(i+1)%n]);
        ta+= abs(ccw(pt, pol[i], pol[(i+1)%n]));
    }

    return abs(abs(ra) - ta) < EPS;
}

PTX intersection(const PTX &a0, const PTX &a1, const PTX &b0, const PTX &b1) {
    f64 an, am, bn, bm, x, y;

    if(abs(a0.x - a1.x) < EPS) {
        bn = (b0.y - b1.y) / (b0.x - b1.x);
        bm = b0.y - b0.x * bn;

        return PTX(a0.x, a0.x * bn + bm);
    }
    else {
        if(abs(b0.x - b1.x) < EPS) {
            an = (a0.y - a1.y) / (a0.x - a1.x);
            am = a0.y - a0.x * an;

            return PTX(b0.x, an * b0.x + am);
        }
        else {
            an = (a0.y - a1.y) / (a0.x - a1.x);
            am = a0.y - a0.x * an;

            bn = (b0.y - b1.y) / (b0.x - b1.x);
            bm = b0.y - b0.x * bn;

            return PTX((bm - am)/(an - bn) , (bm - am)/(an - bn) * an + am);
        }
    }
}

vector<PTX> make_hull(vector<PTX> ptr) {
    vector<PTX> hull, ue, le;

    sort(ptr.begin(), ptr.end());
    ptr.resize(unique(ptr.begin(), ptr.end())-ptr.begin());

    for(int i=0; i<ptr.size(); ++i) {
        while(ue.size()>=2 && ccw(ue[ue.size()-2], ue[ue.size()-1], ptr[i])>EPS)
            ue.pop_back();
        while(le.size()>=2 && ccw(le[le.size()-2], le[le.size()-1], ptr[i])<-EPS)
            le.pop_back();
        ue.push_back(ptr[i]);
        le.push_back(ptr[i]);
    }
    for(int i=0; i<ue.size(); ++i)
        hull.push_back(ue[i]);
    for(int i=le.size()-2; i>0; --i)
        hull.push_back(le[i]);

    return hull;
}

vector<PTX> common(vector<PTX> pa, vector<PTX> pb) {
    int n, m;
    vector<PTX> res;

    n = pa.size();
    m = pb.size();

    for(int i=0; i<n; ++i) {
    for(int j=0; j<m; ++j) {
        if(intersect(pa[i], pa[(i+1)%n], pb[j], pb[(j+1)%m]))
            res.push_back(intersection(pa[i], pa[(i+1)%n], pb[j], pb[(j+1)%m]));
    } }
    for(int i=0; i<n; ++i)
        if(inside(pa[i], pb))
            res.push_back(pa[i]);
    for(int i=0; i<m; ++i)
        if(inside(pb[i], pa))
            res.push_back(pb[i]);

    return res;
}

int main(void) {
    ifstream fi("arie.in");
    ofstream fo("arie.out");
    int n, m;
    f64 x, y, srf;

    fi >> n;
    for(int i=1; i<=n; ++i) {
        fi >> x >> y;
        pa.push_back(PTX(x, y));
    }
    fi >> m;
    for(int j=1; j<=m; ++j) {
        fi >> x >> y;
        pb.push_back(PTX(x, y));
    }

    pa = make_hull(pa); // just to make sure
    pb = make_hull(pb);

    res = common(pa, pb);

    res = make_hull(res);
    srf = take_area(res);

    fo << setprecision(3) << fixed << srf << '\n';

    return 0;
}