Cod sursa(job #781736)

Utilizator tzipleatudTudor Tiplea tzipleatud Data 24 august 2012 23:11:43
Problema Camera Scor 10
Compilator cpp Status done
Runda Lista lui wefgef Marime 2.45 kb
#include <fstream>
#include <vector>
#include <iomanip>
#include <cmath>
#define x first
#define y second
#define NM 2010
#define EPS 0.000001
#define INF 99999999

using namespace std;

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

typedef pair<double, double> PD;

PD V[NM];
int N,i,j,Sign[NM],M,a,b,c;
vector<PD> PLG,PLX;
double ANS;

inline int FindSign (const PD& P1, const PD& P2, const PD& P3)
{
    double S=P1.x*P2.y+P2.x*P3.y+P3.x*P1.y-P1.x*P3.y-P2.x*P1.y-P3.x*P2.y;
    return (S>EPS?1:(S<-EPS?-1:0));
}

void Intersect (const PD& P, const PD& Q, const PD& R, const PD& S)
{
    double A1,B1,C1,A2,B2,C2,D;

    A1=Q.y-P.y;
    B1=P.x-Q.x;
    C1=A1*P.x+B1*P.y;

    A2=S.y-R.y;
    B2=R.x-S.x;
    C2=A2*R.x+B2*R.y;

    D=A1*B2-A2*B1;

    if (fabs(D)<EPS)
    {
        //PLX.push_back(make_pair(-INF,-INF));
        return;
    }

    PLX.push_back(make_pair((B2*C1-B1*C2)/D,(A1*C2-A2*C1)/D));
    return;
}

double Solve (int Sg)
{
    PLG.clear();
    PLG.push_back(make_pair(-INF,-INF));
    PLG.push_back(make_pair(-INF,INF));
    PLG.push_back(make_pair(INF,INF));
    PLG.push_back(make_pair(INF,-INF));

    for (i=1; i<=N; i++)
    {
        PLX.clear();
        M=PLG.size();
        for (j=0; j<M; j++)
            Sign[j]=FindSign(V[i],V[i+1],PLG[j]);

        for (j=0; j<M; j++)
        {
            a=j;
            b=j+1;
            if (b>M) b-=M;
            if (Sign[a]*Sg<=0 && Sign[b]*Sg<=0)
            {
                PLX.push_back(PLG[b]);
            }
            if (Sign[a]*Sg<=0 && Sign[b]*Sg>0)
            {
                Intersect(V[i],V[i+1],PLG[a],PLG[b]);
            }
            if (Sign[a]*Sg>0 && Sign[b]*Sg>0) continue;
            if (Sign[a]*Sg>0 && Sign[b]*Sg<=0)
            {
                Intersect(V[i],V[i+1],PLG[a],PLG[b]);
                PLX.push_back(PLG[b]);
            }
        }

        PLG=PLX;
    }

    double ANS=0;
    M=PLG.size();

    for (i=0; i<M; i++)
    {
        a=i-1;
        if (a<0) a+=M;

        b=i;

        c=i+1;
        if (c>M) c-=M;

        ANS+=PLG[b].x*PLG[c].y-PLG[b].x*PLG[a].y;
    }

    ANS=max(ANS,-ANS);
    return ANS/2.0;
}

int main ()
{
    f >> N;
    for (i=1; i<=N; i++)
        f >> V[i].x >> V[i].y;
    V[N+1]=V[1];

    ANS=max(Solve(1),Solve(-1));

    g << fixed << setprecision(3) << ANS << '\n';
    f.close();
    g.close();
    return 0;
}