Cod sursa(job #1412437)

Utilizator danalex97Dan H Alexandru danalex97 Data 1 aprilie 2015 12:02:47
Problema Camera Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.56 kb
#include <iostream>
#include <cmath>
#include <fstream>
#include <iomanip>
#include <vector>
using namespace std;

const double eps = 1e-12;
const int max_int = 100010;

ifstream F("camera.in");
ofstream G("camera.out");

pair<double,double> nowhere = make_pair(-max_int*2,-max_int*2);

#define x first
#define y second

int n;
vector< pair<double,double> > polygon,new_polygon;
vector< pair<double,double> > points;

double area(vector< pair<double,double> > v)
{
    double ans = 0;
    for (int i=0;i<int(v.size())-1;++i)
        ans += v[i].x * v[i+1].y - v[i+1].x * v[i].y;
    return ans/2;
}

int sign(pair<double,double> p1,pair<double,double> p2,pair<double,double> p3)
{
    double a = p1.y - p2.y;
    double b = p2.x - p1.x;
    double c = - p2.x * p1.y - p1.x * p2.y;
    if ( p3.x * a + p3.y * b + c < 0 )
        return -1;
    return 1;
}

pair<double,double> intersection(pair<double,double> p1,pair<double,double> p2,pair<double,double> p3,pair<double,double> p4)
{
    double a1 = p1.y - p2.y;
    double b1 = p2.x - p1.x;
    double c1 = - p1.y * p2.x + p2.y * p1.x;

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

    double d = a1*b2 - a2*b1;

    if ( fabs(d) < eps )
        return nowhere;
    double xx = -(b2*c1-b1*c2)/d;
    double yy = b1 != 0 ? (- a1 * xx - c1) / b1 : (- a2 * xx - c2) / b2;

    return make_pair(xx,yy);
}

int main()
{
    F>>n;
    for (int i=1,x,y;i<=n;++i)
    {
        F>>x>>y;
        points.push_back(make_pair(x,y));
    }
    points.push_back(points[0]);
    int sgn = area(points) > 0 ? 1 : -1;

    polygon.push_back(make_pair(-max_int,max_int));
    polygon.push_back(make_pair(max_int,max_int));
    polygon.push_back(make_pair(max_int,-max_int));
    polygon.push_back(make_pair(-max_int,-max_int));
    polygon.push_back(make_pair(-max_int,max_int));
    for (int i=0;i<n;++i)
    {
        new_polygon = vector< pair<double,double> >();
        for (int j=0;j<int(polygon.size())-1;++j)
        {
            int sign1 = sign(points[i],points[i+1],polygon[j]);
            int sign2 = sign(points[i],points[i+1],polygon[j+1]);
            if ( sign1 == sgn && sign2 == sgn )
                new_polygon.push_back( polygon[j+1] );
            if ( sign1 == sgn && sign2 == -sgn )
            {
                pair<double,double> what = intersection(points[i],points[i+1],polygon[j],polygon[j+1]);
                if ( -max_int <= what.x && what.x <= max_int && -max_int <= what.y && what.y <= max_int ) new_polygon.push_back( what );
                //if ( what != nowhere ) new_polygon.push_back( what );
            }
            if ( sign1 == -sgn && sign2 == sgn )
            {
                pair<double,double> what = intersection(points[i],points[i+1],polygon[j],polygon[j+1]);
                if ( -max_int <= what.x && what.x <= max_int && -max_int <= what.y && what.y <= max_int ) new_polygon.push_back( what );
                //if ( what != nowhere ) new_polygon.push_back( what );
                new_polygon.push_back( polygon[j+1] );
            }
            if ( new_polygon.size() > 1 )
            {
                vector<pair<double,double> >::iterator it = new_polygon.end(); --it;--it;
                if ( new_polygon.back() == *it )
                    new_polygon.pop_back();
            }
        }
        polygon = new_polygon;
        polygon.push_back(polygon[0]);
    }

    double ans = area(polygon);
    if ( ans < 0 ) ans = -ans;
    G<<fixed<<setprecision(3)<<ans<<'\n';
}