Cod sursa(job #1494948)

Utilizator alex_HarryBabalau Alexandru alex_Harry Data 2 octombrie 2015 00:22:32
Problema Camera Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.51 kb
#include <fstream>
#include <vector>
#include <iomanip>
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 = 1e-5;
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;
    double x,y;
    Coef(A2,B2,C2,p,p2);
    if(A2!=0)
    {
        double number=A/A2;
    B2*=number;
    C2*=number;

    y=(C2-C)/(B-B2);
    x=(-C-y*B)/A;
    }
    else
    {
        y=(-C2)/B2;
        x=(-C-B*y)/A;
    }
    return make_pair(x,y);
}
void 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=max(Area,-Area);
    g<<fixed<<setprecision(2)<<Area<<"\n";
}
int main()
{
    Read();
    Solve();
    return 0;
}