Cod sursa(job #2301472)

Utilizator Mihai_PredaPreda Mihai Dragos Mihai_Preda Data 12 decembrie 2018 23:57:15
Problema Camera Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.77 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <cmath>

using namespace std;

const double eps = 1e-5;

struct Punct
{
    Punct(double x = 0.0, double y = 0.0)
    {
        this->x = x;
        this->y = y;
    }
    double x, y;
};

double det(const Punct &a, const Punct &b, const Punct &c)
{
    return (b.x - a.x) * (c.y - a.y) -  (b.y - a.y)*(c.x - a.x);
}

int sign(double x)
{
    if(x > eps)
        return 1;
    if(x < -eps)
        return -1;
    return 0;
}

Punct intersect(const Punct &a, const Punct &b, const Punct &c, const Punct &d)
{
    double a1 = b.y - a.y;
	double b1 = a.x - b.x;
	double c1 = b.x*a.y - a.x*b.y;

	double a2 = d.y - c.y;
	double b2 = c.x - d.x;
	double c2 = d.x*c.y - c.x*d.y;

	double div = a1*b2 - a2*b1;
	double x = (b1*c2 - b2*c1) / div;
	double y = (a2*c1 - a1*c2) / div;

	return Punct(x, y);
}

void CutPol(const Punct &a, const Punct &b, vector<Punct> &pol)
{
    vector<Punct> ret;
    int s1, s2;
    Punct I;
    for(int i = 0; i < pol.size(); ++i)
    {
        auto &cur = pol[i], &urm = pol[(i+1) % pol.size()];
        s1 = sign(det(cur, a, b)), s2 = sign(det(urm, a, b));
        if(s1 * s2 < 0)
        {
            I = intersect(cur, urm, a, b);

            if(s1 > 0)
            {
                ret.push_back(cur);
                ret.push_back(I);
            }
            else
            {
                ret.push_back(I);
                ret.push_back(urm);
            }
        }
        else if(s1 >= 0)
            ret.push_back(pol[i]);
    }

    pol = ret;
}

double GetArea(const vector<Punct> &pol)
{
    double ret = 0;
    Punct O(0, 0);
    for(int i = 1; i < pol.size(); ++i)
        ret += det(O, pol[i-1], pol[i]);
    ret += det(O, pol.back(), pol[0]);
    ret /= 2;
    return ret;
}

int main()
{
    ifstream in("camera.in");
    int n;
    in >> n;
    vector<Punct> v(n);
    for(auto &p:v)
        in >> p.x >> p.y;
    in.close();

    double minX = v[0].x, minY = v[0].y, maxX = v[0].x, maxY = v[0].y;

    for(int i = 1; i < n; ++i)
    {
        minX = min(minX, v[i].x);
        minY = min(minY, v[i].y);
        maxX = max(maxX, v[i].x);
        maxY = max(maxY, v[i].y);
    }

    if(GetArea(v) < 0)
        reverse(v.begin(), v.end());

    vector<Punct> pol;
    pol.push_back(Punct(minX, minY));
    pol.push_back(Punct(maxX, minY));
    pol.push_back(Punct(maxX, maxY));
    pol.push_back(Punct(minX, maxY));

    for(int i = 1; i < n; ++i)
        CutPol(v[i-1], v[i], pol);
    CutPol(v[n-1], v[0], pol);

    ofstream out("camera.out");
    out << fixed << setprecision(2) << fabs(GetArea(pol)) << "\n";
    out.close();
    return 0;
}