Cod sursa(job #2051747)

Utilizator Coroian_DavidCoroian David Coroian_David Data 29 octombrie 2017 15:00:40
Problema Camera Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 3.72 kb
///x == 0 <=> -epsilon < x < epsilon

/**
*   Tinem poligonul solutie sub forma de puncte.
*   O dreapta daca intersecteaza poligonul o face in 2 puncte.
*   Daca intersecteaza tinem intersectia.
*
*   Time Complexity : O(N^2);
*
*   COROIAN DAVID, Satu Mare, ROMANIA
**/

#include <bits/stdc++.h>

#define MAX_N 2000

using namespace std;

FILE *f;

int n;

struct coord
{
    long double x, y;
};

coord v[MAX_N + 2];

coord s[MAX_N + 2];
coord sn[MAX_N + 2];

const long double epsilon = 0.000001D;

int sign(long double x)
{
    if(-epsilon < x && x < epsilon)
        return 0;

    if(x > 0)
        return 1;

    if(x < 0)
        return -1;

    return 0;
}

void readFile()
{
    s[1] = {100000, 100000};///st jos
    s[2] = {-100000, 100000};///dr jos
    s[3] = {-100000, -100000};///dr sus
    s[4] = {100000, -100000};///st sus

    f = fopen("camera.in", "r");

    fscanf(f, "%d", &n);

    int i;
    long double ld = 1.0D;
    int x, y;
    for(i = 1; i <= n; i ++)
    {
        fscanf(f, "%d%d", &x, &y);

        v[i] = {ld * x, ld * y};

        s[1].x = s[4].x = min(s[1].x, ld * x);
        s[2].x = s[3].x = max(s[2].x, ld * x);

        s[1].y = s[2].y = min(s[1].y, ld * y);
        s[3].y = s[4].y = max(s[3].y, ld * y);
    }

    long double a = 0;
    v[n + 1] = v[1];
    for(i = 1; i <= n; i ++)
        a += v[i].x * v[i + 1].y - v[i].y * v[i + 1].x;

    if(a < 0)
    {
        int mid = n >> 1;
        for(i = 1; i <= mid; i ++)
            swap(v[i], v[n - i + 1]);
    }

    v[n + 1] = v[1];

    fclose(f);
}

long double aria(coord a, coord b, coord c)
{
    ///x1 y1
    ///x2 y2
    ///1/2 *
    return a.x * b.y - a.y * b.x +
           b.x * c.y - b.y * c.x +
           c.x * a.y - c.y * a.x;
}

void getABC(coord p1, coord p2, long double &a, long double &b, long double &c)
{
    a = p2.y - p1.y;
    b = p1.x - p2.x;
    c = p2.x * p1.y - p1.x * p2.y;
}

coord getInter(coord p1, coord p2, coord p3, coord p4)
{
    long double a, b, c;
    long double d, e, f;

    getABC(p1, p2, a, b, c);
    getABC(p3, p4, d, e, f);

    coord rez;
    rez.y = (c * d - f * a) / (e * a - b * d);
    rez.x = (-c * e + f * b) / (e * a - b * d);

    return rez;
}

long double getRez()
{
    int k = 4;

    long double ar1;
    long double ar2;
    int i, j;
    for(i = 1; i <= n; i ++)
    {
        coord d1, d2;
        d1 = v[i];
        d2 = v[i + 1];

        int nk = 0;
        s[k + 1] = s[1];
        for(j = 1; j <= k; j ++)
        {
            coord a, b;
            a = s[j];
            b = s[j + 1];

            ar1 = aria(d1, d2, a);
            ar2 = aria(d1, d2, b);

            if(sign(ar1) * sign(ar2) < 0.0D)
            {
                sn[++ nk] = getInter(d1, d2, a, b);

                if(sign(ar2) > 0)///Nu punem acelasi punct de 2 ori
                    sn[++ nk] = b;
            }

            else
                if(sign(ar2) >= 0)
                    sn[++ nk] = b;
        }

        for(j = 1; j <= nk; j ++)
            s[j] = sn[j];

        k = nk;
    }

    long double rez = 0.0D;
    s[k + 1] = s[1];
    for(i = 1; i <= k; i ++)
        rez += s[i].x * s[i + 1].y - s[i].y * s[i + 1].x;

    if(rez != 0.0D)
    {
        rez = fabsl(rez);
        rez /= 2.0D;
    }

    return rez;
}

long double rez;

void solve()
{
    ///Se intampla undefined daca bagi 2 functii in aceeasi linie de cod.
    rez = getRez();
}

void printFile()
{
    ofstream g("camera.out");

    g << fixed << setprecision(2) << rez << "\n";

    g.close();
}

int main()
{
    readFile();

    solve();

    printFile();

    return 0;
}