Cod sursa(job #1905571)

Utilizator andrei_diaconuAndrei Diaconu andrei_diaconu Data 6 martie 2017 09:22:50
Problema Camera Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.71 kb
#include <fstream>
#include <algorithm>
#include <string.h>

#define NMax 2010
#define INF 1000000
#define eps 0.0000001

using namespace std;

ifstream f("camera.in");
ofstream g("camera.out");

struct Point {
    double x;
    double y;

    Point() {};
    Point(double _x, double _y) {
        x = _x;
        y = _y;
    }
} polyg[NMax], crt[NMax], nex[NMax];

int n, nP, newNP;

double mabs(double d1)
{
    if (d1 < 0)
        return -d1;
    return d1;
}

int det(Point p1, Point p2, Point p3)
{
    return p1.x*p2.y + p2.x*p3.y + p3.x*p1.y - p3.x*p2.y - p1.x*p3.y - p2.x*p1.y;
}

double tri_area(Point p1, Point p2)
{
    return p1.x*p2.y - p2.x*p1.y;
}

Point get_intersection_coords(Point p1, Point p2, Point p3, Point p4) //grija la paralele
{
    double a1 = p2.y - p1.y;
    double b1 = p1.x - p2.x;
    double c1 = p1.y*p2.x - p1.x*p2.y;

    double a2 = p4.y - p3.y;
    double b2 = p3.x - p4.x;
    double c2 = p3.y*p4.x - p3.x*p4.y;

    Point answ;
    answ.x = (b2*c1 - b1*c2) / (a1*b2 - a2*b1);
    answ.y = (a1*c2 - a2*c1) / (a1*b2 - a2*b1);

    return answ;
}

int dist(Point p1, Point p2)
{
    return (p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y);
}

bool intersect(Point p1, Point p2, Point p3, Point p4)
{
    double d1 = det(p1, p3, p2);
    double d2 = det(p1, p4, p2);
    double d3 = det(p3, p1, p4);
    double d4 = det(p3, p2, p4);

    if (d1*d2 < 0 || d3*d4 < 0)
        return true;
    return false;
}

bool equal_double(double d1, double d2)
{
    if (mabs(d1 - d1) <= eps)
        return true;
    return false;
}

int main()
{
    f >> n;

    Point leftCorner(INF, INF), rightCorner(0, 0), lowest;
    for (int i = 1; i <= n; i++) {
        f >> polyg[i].x >> polyg[i].y;

        if (leftCorner.x > polyg[i].x)
            leftCorner.x = polyg[i].x;
        if (leftCorner.y > polyg[i].y)
            leftCorner.y = polyg[i].y;
        if (rightCorner.x < polyg[i].x)
            rightCorner.x = polyg[i].x;
        if (rightCorner.y < polyg[i].y)
            rightCorner.y = polyg[i].y;
    }
    crt[++nP] = Point(leftCorner.x, leftCorner.y);
    crt[++nP] = Point(rightCorner.x, leftCorner.y);
    crt[++nP] = Point(rightCorner.x, rightCorner.y);
    crt[++nP] = Point(rightCorner.x, leftCorner.y);
    crt[++nP] = crt[1];

    polyg[n + 1] = polyg[1];
    double area = 0;
    for (int i = 1; i <= n; i++)
        area += tri_area(polyg[i], polyg[i+1]);

    if (area < 0)
        for (int i = 1; i <= n / 2; i++)
            swap(polyg[i], polyg[n - i + 1]);
    polyg[n + 1] = polyg[n];

    for (int i = 1; i <= n; i++) { //pol edges
        Point p1 = polyg[i];
        Point p2 = polyg[i + 1];
        for (int j = 1; j <= nP; j++) { //answ edg
            Point p3 = crt[j];
            Point p4 = crt[j + 1];

            if (intersect(p1, p2, p3, p4) == true) {
                Point intersection = get_intersection_coords(p1, p2, p3, p4);

                if (det(p1, p2, p4) < 0) {
                    nex[++newNP] = intersection;
                    nex[++newNP] = p4;
                }
                else
                    nex[++newNP] = intersection;

            }
            else {
                if (det(p1, p2, p3) <= 0)
                    nex[++newNP] = p3;
                if (det(p1, p2, p4) <= 0)
                    nex[++newNP] = p4;
            }
        }

        nP = newNP;
        newNP = 0;
        swap(crt, nex);
        crt[nP + 1] = crt[1];
        memset(nex, 0, sizeof(nex));
    }

    double answArea = 0;
    for (int i = 1; i <= n; i++)
        answArea += tri_area(crt[i], crt[i+1]);

    g << 1.0 * answArea / 2;

    return 0;
}