Cod sursa(job #2977765)

Utilizator gabriel10tm@gmail.comGabriel Marian [email protected] Data 12 februarie 2023 13:30:14
Problema Reuniune Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.64 kb
#include <bits/stdc++.h>
using namespace std;
#define ll int64_t
#define ull uint64_t
typedef array<ll,2> P;
typedef array<ll,4> R;
#if 1
#define cin fin
#define cout fout
ifstream fin("reuniune.in");
ofstream fout("reuniune.out");
#endif // 0
R rec[3];
array<P,4> getPts(R r){
    return {P{r[0],r[1]},P{r[2],r[3]},P{r[0],r[3]},P{r[2],r[1]}};
}
bool isPInR(R r, P p){
    return r[0] <= p[0] && p[0] <= r[2] && r[1] <= p[1] && p[1] <= r[3];
}
ull area(R r){
    return (ull)abs(r[2]-r[0])*abs(r[3]-r[1]);
}
ull peri(R r){
    return 2*(abs(r[2]-r[0])+abs(r[3]-r[1]));
}
ull area(P p0, P p1){
    return (ull)abs(p1[0]-p0[0])*abs(p1[1]-p0[1]);
}
R rect(P p0,P p1){
    return {min(p0[0],p1[0]),min(p0[1],p1[1]),max(p0[0],p1[0]),max(p0[1],p1[1])};
}
R overlap(R r1, R r2){
    vector<P> m;
    vector<P> oth;
    auto rp1 = getPts(r1), rp2 = getPts(r2);
    for(P p : rp2)
        if(isPInR(r1,p))
            m.push_back(p);
        else
            oth.push_back(p);
    if(m.size()==4){
        return r2;
    }
    if(m.size()==1){
        P p1 = {INT_MAX,INT_MAX};
        for(P p : rp1)
            if(isPInR(r2,p))
                p1 = p;

        assert(p1[0]!=INT_MAX);
        return rect(p1,m[0]);
    }
    if(m.size()==2){
        P p1, p2;
        if(m[0][0] == m[1][0]){ /// x0=x1 => vertical points
            if(abs(oth[0][0]-r1[0])<abs(oth[0][0]-r1[2]))
                p1 = m[0], p2 = {r1[0],m[1][1]};
            else
                p1 = m[0], p2 = {r1[2],m[1][1]};
        }
        else{ /// horizontal points
            if(abs(oth[0][1]-r1[1])<abs(oth[0][1]-r1[3]))
                p1 = m[0], p2 = {m[1][0],r1[1]};
            else
                p1 = m[0], p2 = {m[1][0],r1[3]};
        }
        return rect(p1,p2);
    }
    return {0,0,0,0};
}

ll ovp(R r1,R r2){
    return max(peri(overlap(r1,r2)),peri(overlap(r2,r1)));
}

ll ovp(R r1,R r2,R r3){
    R i1 = overlap(r1,r2), i2 = overlap(r2,r1);
    return max(ovp(i1,r3),ovp(i2,r3));
}

ull ova(R r1,R r2){
    return max(area(overlap(r1,r2)),area(overlap(r2,r1)));
}

ull ova(R r1,R r2,R r3){
    R i1 = overlap(r1,r2), i2 = overlap(r2,r1);
    return max(ova(i1,r3),ova(i2,r3));
}


int main(){
    for(int i=0;i<3;i++){
        cin >> rec[i][0] >> rec[i][1] >> rec[i][2] >> rec[i][3];
    }
    ull ta = area(rec[0]) + area(rec[1]) + area(rec[2]) - ova(rec[0],rec[1]) - ova(rec[1],rec[2]) - ova(rec[2],rec[0]) + ova(rec[0],rec[1],rec[2]);
    ull tp = peri(rec[0]) + peri(rec[1]) + peri(rec[2]) - ovp(rec[0],rec[1]) - ovp(rec[1],rec[2]) - ovp(rec[2],rec[0]) + ovp(rec[0],rec[1],rec[2]);

    cout << ta << " " << tp;
}