Cod sursa(job #918107)

Utilizator apopeid13Apopeid Alejandro apopeid13 Data 18 martie 2013 17:18:56
Problema Camera Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.34 kb
#include <fstream>
#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;
 
ifstream fin("camera.in");
ofstream fout("camera.out");
 
const int MAXN = 2100;
const int INF = 210000;
const int EPS = 0.000001;
 
struct point {
    double x, y;
};
 
point make_point(int x, int y) {
    point a;
    a.x = x;
    a.y = y;
    return a;
}
 
double cross_point(point p1, point p2, point p3) {
    return p1.x * p2.y + p2.x * p3.y + p3.x * p1.y - p2.x * p1.y - p3.x * p2.y - p1.x * p3.y;
}
 
double get_arie(point points[], int N) {
    double arie = 0;
    point p0 = make_point(0, 0);
 
    for (int i = 1; i <= N; ++i)
        arie += cross_point(p0, points[i], points[i + 1]);
    return arie / 2;
}
 
void coef(point A, point B, double &a, double &b, double &c) {
    a = B.y - A.y;
    b = A.x - B.x;
    c = B.x * A.y - A.x * B.y;
}
 
point intersection(point p1, point p2, point p3, point p4) {
    double a1, a2, b1, b2, c1, c2;
    coef (p1, p2, a1, b1, c1);
    coef (p3, p4, a2, b2, c2);
 
    point a;
    a.x = (c2 * b1 - c1 * b2) / (a1 * b2 - a2 * b1);
    a.y = (a1 * c2 - a2 * c1) / (a2 * b1 - a1 * b2);
    return a;
 
}
 
int N, M, P;
point A[MAXN], B[MAXN], C[MAXN];
 
int main() {
    fin >> N;
 
    for (int i = 1; i <= N; ++i)
        fin >> A[i].x >> A[i].y;
    A[N + 1] = A[1];
 
    M = 4;
    B[1] = make_point(-INF, INF);
    B[2] = make_point(INF, INF);
    B[3] = make_point(INF, -INF);
    B[4] = make_point(-INF, -INF);
    B[5] = B[1];
 
    int sign = get_arie(A, N) > 0 ? -1 : 1;
 
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= M; ++j) {
            int s1 = cross_point(A[i], A[i + 1], B[j]) > 0 ? -1 : 1;
            int s2 = cross_point(A[i], A[i + 1], B[j + 1]) > 0 ? -1 : 1;
 
            if (s1 == sign && s2 == sign)
                C[++P] = B[j + 1];
            if (s1 == sign && s2 != sign)
                C[++P] = intersection(A[i], A[i + 1], B[j], B[j + 1]);
            if (s1 != sign && s2 == sign) {
                C[++P] = intersection(A[i], A[i + 1], B[j], B[j + 1]);
                C[++P] = B[j + 1];
            }
        }
        for (int i = 1; i <= P; ++i)
            B[i] = C[i];
        B[P + 1] = B[1]; M = P; P = 0;
    }
 
    fout << fixed << setprecision(2) << abs(get_arie(B, M));
    return 0;
}