Cod sursa(job #1494945)

Utilizator alex_HarryBabalau Alexandru alex_Harry Data 2 octombrie 2015 00:15:41
Problema Camera Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.6 kb
#include <fstream>
#include <vector>
#include <iomanip>
#include <algorithm>
#include <cmath>
using namespace std;
ifstream f("camera.in");
ofstream g("camera.out");
int N;
pair <double,double> Point[2005];
vector <pair <double,double> > Sol,newSol;
const double eps = 0.000001;
const double INF = 1000000;
void Read()
{
    f>>N;
    for(int i=1;i<=N;i++)
        f>>Point[i].first>>Point[i].second;
    Point[N+1]=Point[1];
}
int getSign(double A,double B,double C,pair<double,double> p)
{
    double res=A*p.first+B*p.second+C;
    if(res<-eps)
        return -1;
    if(res>eps)
        return 1;
    return 0;
}

void Coef(double& A,double& B,double& C,pair<double,double>p1,pair<double,double> p2)
{
    A=p2.second-p1.second;
    B=p1.first-p2.first;
    C=p2.first*p1.second-p2.second*p1.first;
}

pair<double,double> Intersect(double A,double B,double C,pair<double,double> p,pair<double,double>p2)
{
    double A2, B2, C2;
    Coef( A2, B2, C2, p, p2 );

    double det = A * B2 - A2 * B;
    double X = (B * C2 - B2 * C) / det;
    double Y = (A2 * C - A * C2) / det;

    return make_pair(X, Y);
}
double Solve()
{
    Sol.push_back(make_pair(-INF,-INF));
    Sol.push_back(make_pair(-INF,INF));
    Sol.push_back(make_pair(INF,INF));
    Sol.push_back(make_pair(INF,-INF));
    Sol.push_back(make_pair(-INF,-INF));
    for(int i=1;i<=N;i++)
    {
        double A,B,C;
        Coef(A,B,C,Point[i],Point[i+1]);
        for(int k=0;k+1<Sol.size();k++)
        {
            int sgn=getSign(A,B,C,Sol[k]);
            int sgn2=getSign(A,B,C,Sol[k+1]);
            if(sgn<0 && sgn2<0)
                continue;
            if(sgn>=0 && sgn2>=0)
            {
                newSol.push_back(Sol[k]);
            }
            if(sgn<0 && sgn2>=0)
            {
                newSol.push_back(Intersect(A,B,C,Sol[k],Sol[k+1]));
            }
            if(sgn>=0 && sgn2<0)
            {
                newSol.push_back(Sol[k]);
                if(sgn>0)
                    newSol.push_back(Intersect(A,B,C,Sol[k],Sol[k+1]));
            }
        }
        newSol.push_back(newSol[0]);
        Sol=newSol;
        newSol.clear();
    }
    double Area=0;
    for(int i=0;i+1<Sol.size();i++)
    {
        Area+=Sol[i].first*Sol[i+1].second-Sol[i+1].first*Sol[i].second;
    }
    Area/=2;
    Area=fabs(Area);
    return Area;
}
int main()
{
    Read();
    double area=Solve();
    if(area<eps)
    {
        reverse(Point+1,Point+N+1);
        Sol.clear();
        area=Solve();
    }
    g<<fixed<<setprecision(2)<<area<<"\n";
    return 0;
}