Cod sursa(job #986284)

Utilizator Impaler_009Mihai Nitu Impaler_009 Data 18 august 2013 14:01:40
Problema Camera Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.37 kb
#include <fstream>
#include <utility>
#include <cmath>
#include <iomanip>
#include <algorithm>

#define maxn 2001
#define inf 100001
#define eps 1e-6
#define x first
#define y second

using namespace std;

ifstream fin ("camera.in");
ofstream fout ("camera.out");

typedef pair<double,double> point;

point p[maxn],temp[maxn],v[maxn];
int sgn[maxn];
int t,n,m;

int what_side (double a, double b, double c, point P)
{
    double d = a*P.x + b*P.y +c;
    if (d<-eps) return -1;
    if (d>eps) return 1;
    return 0;
}

void get_coefficients (point p1, point p2, double &a, double &b, double &c)
{
        a = p2.y - p1.y;
        b = p1.x - p2.x;
        c = p2.x*p1.y - p1.x*p2.y;
}

point intersection (double a1, double b1, double c1, point p1, point p2)
{
    double a2,b2,c2; point P;
    get_coefficients (p1,p2,a2,b2,c2);
    double det = a1*b2-a2*b1;
    P.x = (b1*c2-b2*c1)/det;
    P.y = (a2*c1-a1*c2)/det;
    return P;
}

double area (point p[], int size)
{
    double A=0;
    for (int i=1; i<=size; ++i)
    {
        int ii; i==size ? ii=1 : ii=i+1;
        A += p[i].x*p[ii].y - p[ii].x*p[i].y;        // formula ariei cu un punct de reper aflat in afara planului (0,-inf). Ne ajuta sa determinam sensul punctelor triunghiului (A NU SE FOLOSI UN PUNCT OARECARE PT. ACEASTA DETERMINARE)
    }
    return A;
}

int main()
{
    fin>>n;
    for (int i=1; i<=n; ++i)
        fin>>v[i].x>>v[i].y;

    t=4;
    p[1].x=inf; p[1].y=inf;
    p[2].x=inf; p[2].y=-inf;
    p[3].x=-inf; p[3].y=-inf;
    p[4].x=-inf; p[4].y=inf;

    double S = area(v,n);
    if (S>eps) reverse (v+1,v+n+1);

    for (int i=1; i<=n; ++i)
    {
        int ii; i==n ? ii=1 : ii=i+1;

        double a,b,c;
        get_coefficients (v[i],v[ii],a,b,c);

        for (int j=1; j<=t; ++j)
           sgn[j] = what_side (a,b,c,p[j]);

        int te=0;

        for (int j=1; j<=t; ++j)
        {
            int jj; j==t ? jj=1 : jj=j+1;
            if (sgn[j]>=0 && sgn[jj]>=0) temp[++te]=p[j];
            else if (sgn[j]<0 && sgn[jj]>=0) temp[++te]= intersection (a,b,c,p[j],p[jj]);
            else if (sgn[j]>=0 && sgn[jj]<0)  temp[++te]=p[j],temp[++te]= intersection (a,b,c,p[j],p[jj]);
        }

        t=te;
        for (int j=1; j<=t; ++j) p[j]=temp[j];
    }

    double A=area(p,t);
    fout<<fixed<<setprecision(2)<<fabs(A/2);
}