Cod sursa(job #1829914)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu Data 15 decembrie 2016 20:36:48
Problema Camera Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.33 kb
#include<fstream>
#include<iomanip>
#define x first
#define y second
#define eps 0.000001
using namespace std;
int n, i, j, nr, nr1, ok;
double d1, d2, aria, xmin, xmax, ymin, ymax;
pair<double, double> v[2005], p[6005], aux[6005], pct, a, b;
ifstream fin("camera.in");
ofstream fout("camera.out");
double det(pair<double, double> p1, pair<double, double> p2, pair<double, double> p3){
    return (p2.x - p1.x) * (p3.y - p1.y) - (p3.x - p1.x) * (p2.y - p1.y);
}
pair<double, double> intersect(pair<double, double> p1, pair<double, double> p2, pair<double, double> p3, pair<double, double> p4){
    pair<double, double> p;
    double a1, b1, c1, a2, b2, c2;
    a1 = p2.y - p1.y;
    a2 = p4.y - p3.y;
    b1 = p1.x - p2.x;
    b2 = p3.x - p4.x;
    c1 = -a1 * p1.x - b1 * p1.y;
    c2 = -a2 * p3.x - b2 * p3.y;
    p.x = (c2 * b1 - c1 * b2) / (a1 * b2 - a2 * b1);
    p.y = (c2 * a1 - c1 * a2) / (b1 * a2 - b2 * a1);
    return p;
}
double modul(double x){
    if(x > 0){
        return x;
    }
    return -x;
}
int semn(double x){
    if(modul(x) <= eps){
        return 0;
    }
    else{
        if(x < 0){
            return -1;
        }
        return 1;
    }
}
int main(){
    fin>> n;
    xmin = ymin = 100000;
    xmax = ymax = -100000;
    for(i = 1; i <= n; i++){
        fin>> v[i].x >> v[i].y;
        xmin = min(xmin, v[i].x);
        xmax = max(xmax, v[i].x);
        ymin = min(ymin, v[i].y);
        ymax = max(ymax, v[i].y);
    }
    v[n + 1] = v[1];
    pct = make_pair(0, 0);
    for(i = 1; i <= n; i++){
        aria += det(pct, v[i], v[i + 1]);
    }
    if(aria > 0){
        for(i = 1; i <= n / 2; i++){
            swap(v[i], v[n - i + 1]);
        }
        v[n + 1] = v[1];
    }
    nr = 4;
    p[1] = make_pair(xmin, ymin);
    p[2] = make_pair(xmin, ymax);
    p[3] = make_pair(xmax, ymax);
    p[4] = make_pair(xmax, ymin);
    p[5] = p[1];
    aux[0].x = aux[0].y = 100001;
    for(i = 1; i <= n; i++){
        nr1 = 0;
        for(j = 1; j <= nr; j++){
            d1 = det(v[i], v[i + 1], p[j]);
            d2 = det(v[i], v[i + 1], p[j + 1]);
            d1 = semn(d1);
            d2 = semn(d2);
            ok = 0;
            if(d1 * d2 < 0){
                pct = intersect(v[i], v[i + 1], p[j], p[j + 1]);
                ok = 1;
                if(d1 <= 0){
                    a = p[j];
                    b = pct;
                }
                else{
                    a = pct;
                    b = p[j + 1];
                }
            }
            else{
                if(d1 <= 0 && d2 <= 0){
                    a = p[j];
                    b = p[j + 1];
                    ok = 1;
                }
            }
            if(ok == 1){
                if(aux[nr1] != a){
                    aux[++nr1] = a;
                }
                if( !(j == nr && d2 <= 0) ){
                    aux[++nr1] = b;
                }
            }
        }
        nr = nr1;
        for(j = 1; j <= nr; j++){
            p[j] = aux[j];
        }
        p[nr + 1] = p[1];
    }
    pct = make_pair(0, 0);
    aria = 0;
    for(i = 1; i <= nr; i++){
        aria += det(pct, p[i], p[i + 1]);
    }
    if(aria < 0){
        aria = -aria;
    }
    aria /= 2;
    fout<< setprecision(2) << fixed << aria <<"\n";
    return 0;
}