Cod sursa(job #965974)

Utilizator Florin2Florin Parizer-Fieraru Florin2 Data 25 iunie 2013 00:04:14
Problema Camera Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.5 kb
#include <stdio.h>
#include <algorithm>
#include <cmath>
#define point pair <double, double>
#define x first
#define y second
#define INF 100100

using namespace std;

int N;
point x[2013];

void read() {
    scanf("%d", &N);
    for (int i = 1; i <= N; ++i) {
        int xi, yi;
        scanf("%d%d", &xi, &yi);
        x[i] = make_pair(xi, yi);
    }
    x[N + 1] = x[1];
}

int sgn;
point prev[2013], cur[2013];

double ccw(point A, point B, point C) {
    double ret = (B.x - A.x) * (C.y - B.y) - (B.y - A.y) * (C.x - B.x);
    if (ret > 0.0000001)
        return 1;
    return -1;
}

double det(double A, double B, double C, double D) {
    return A * D - B * C;
}

point intersect(point A, point B, point C, point D) {
    double A1 = A.y - B.y; double B1 = B.x - A.x; double C1 = -A.x * B.y + A.y * B.x;
    double A2 = C.y - D.y; double B2 = D.x - C.x; double C2 = -C.x * D.y + C.y * D.x;
    double xint, yint;
    xint = det(C1, B1, C2, B2) / det(A1, B1, A2, B2);
    yint = det(A1, C1, A2, C2) / det(A1, B1, A2, B2);
    return make_pair(xint, yint);
}

double getArea() {
    int prevCnt = 4;
    prev[1] = make_pair(-INF, -INF);
    prev[2] = make_pair(-INF, INF);
    prev[3] = make_pair(INF, INF);
    prev[4] = make_pair(INF, -INF);
    prev[5] = prev[1];

    int i, j;
    for (i = 1; i <= N; ++i) {
        int curCnt = 0;
        for (j = 1; j <= prevCnt; ++j)
            if (ccw(x[i], x[i + 1], prev[j]) == sgn) {
                cur[++curCnt] = prev[j];
                if (ccw(x[i], x[i + 1], prev[j + 1]) != sgn)
                    cur[++curCnt] = intersect(x[i], x[i + 1], prev[j], prev[j + 1]);
            } else
                if (ccw(x[i], x[i + 1], prev[j + 1]) == sgn)
                    cur[++curCnt] = intersect(x[i], x[i + 1], prev[j], prev[j + 1]);
        if (curCnt == 0)
            return 0;
        prevCnt = curCnt;
        for (j = 1; j <= prevCnt; ++j)
            prev[j] = cur[j];
        prev[prevCnt + 1] = prev[1];
    }

    double area = 0;
    for (i = 1; i <= prevCnt; ++i)
        area += prev[i].x * prev[i + 1].y - prev[i + 1].x * prev[i].y;
    if (area < 0)
        area = -area;
    return area * 0.5;
}

void solve() {
    sgn = 1;
    double area1 = getArea();
    sgn = -1;
    double area2 = getArea();
    printf("%.2lf", area1 > area2 ? area1 : area2);
}

int main() {
    freopen("camera.in", "r", stdin);
    freopen("camera.out", "w", stdout);

    read();
    solve();

    return 0;
}