Cod sursa(job #1116965)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 22 februarie 2014 22:16:55
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 6.01 kb
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cmath>
#include <algorithm>

using namespace std;

const int Nmax = 1000;
const long double eps = 1e-6;

struct Point
{
    long double x, y;

    Point(){}
    Point( long double _x, long double _y ) : x( _x ), y( _y ) {}

    bool operator < ( Point P )
    {
        if ( abs( x - P.x ) > eps )
                return x < P.x;
        else
                return y < P.y;
    }

    long double distance( Point A )
    {
        return sqrt( ( x - A.x ) * ( x - A.x ) + ( y - A.y ) * ( y - A.y ) );
    }

    friend istream& operator >> ( istream &f, Point &P )
    {
        f >> P.x >> P.y;
        return f;
    }

    friend ostream& operator << ( ostream &f, Point P )
    {
        f << P.x << " " << P.y;
        return f;
    }
};

struct Line
{
    long double a, b, c;

    Line(){}
    Line( long double _a, long double _b, long double _c ) : a( _a ), b( _b ), c( _c ) {}
    Line( Point A, Point B )
    {
        a = A.y - B.y;
        b = B.x - A.x;
        c = B.y * A.x - A.y * B.x;
    }

    Point intersection( Line L )
    {
        if ( abs( a * L.b - L.a * b ) < eps )
        {
            return Point( INFINITY, INFINITY );
        }
        else
        {
            long double delta  =  a * L.b - b * L.a;
            long double deltaX = -c * L.b + b * L.c;
            long double deltaY = -a * L.c + c * L.a;

            return Point( deltaX / delta, deltaY / delta );
        }
    }

    friend ostream& operator << ( ostream &f, Line L )
    {
        f << L.a << " " << L.b << " " << L.c;
        return f;
    }
};

struct Segment
{
    Point A, B;

    Segment(){}
    Segment( Point _A, Point _B ) : A( _A ), B( _B ) {}

    int contains( Point P )
    {
        long double dAB = A.distance( B );
        long double dAP = A.distance( P );
        long double dBP = B.distance( P );

        return ( abs( dAB - dAP - dBP ) < eps );
    }

    Point intersection( Segment S )
    {
        return Line( A, B ).intersection( Line( S.A, S.B ) );
    }

    friend ostream& operator << ( ostream &f, Segment S )
    {
        f << S.A << " " << S.B;
        return f;
    }
};

Point A[Nmax], B[Nmax], AB[Nmax + Nmax + Nmax];
long double Area_A, Area_B;

int N, M, NM;

void read( istream &f, Point P[], int &n )
{
    f >> n;

    for ( int i = 1; i <= n; ++i )
            f >> P[i];

    P[n + 1] = P[1];
}

long double CP( Point A, Point B, Point C )
{
    return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}

int PointInPolygon( Point X[], int n, long double areaX, Point P )
{
    long double area = 0;

    for ( int i = 1; i <= n; ++i )
    {
        area += abs( CP( P, X[i], X[i + 1] ) );
    }

    area = abs( area / 2.0 );

    return ( abs( area - areaX ) < eps );
}

void compute_areas()
{
    for ( int i = 2; i < N; ++i )
    {
        Area_A += abs( CP( A[1], A[i], A[i + 1] ) );
    }

    Area_A = abs( Area_A / 2.0 );

    for ( int i = 2; i < M; ++i )
    {
        Area_B += abs( CP( B[1], B[i], B[i + 1] ) );
    }

    Area_B = abs( Area_B / 2.0 );
}

void make_intersection()
{
    for ( int i = 1; i <= N; ++i )
    {
        if ( PointInPolygon( B, M, Area_B, A[i] ) )
        {
            AB[ ++NM ] = A[i];
        }
    }

    for ( int i = 1; i <= M; ++i )
    {
        if ( PointInPolygon( A, N, Area_A, B[i] ) )
        {
            AB[ ++NM ] = B[i];
        }
    }

    for ( int i = 1; i <= N; ++i )
    {
        Segment SA( A[i], A[i + 1] );

        for ( int j = 1; j <= M; ++j )
        {
            Segment SB( B[j], B[j + 1] );

            Point I = SA.intersection( SB );

            ///cout << SA << endl;
            ///cout << SB << endl;
            ///cout << I << "   " << SA.contains( I ) << SB.contains( I ) << endl << endl;

            if ( ( I.x != INFINITY && I.y != INFINITY ) && ( SA.contains( I ) && SB.contains( I ) ) )
            {
                AB[ ++NM ] = I;
            }
        }
    }
}

int cmp( Point A, Point B )
{
    return CP( AB[1], A, B ) < 0.0f;
}

void sort_points()
{
    int pos = 1;

    for ( int i = 2; i <= NM; ++i )
    {
        if ( AB[i] < AB[pos] ) pos = i;
    }

    swap( AB[1], AB[pos] );

    sort( AB + 2, AB + NM + 1, cmp );
}

Point Stiva[Nmax], Polygon[Nmax];
int NP;

void GrahamScan()
{
    sort_points();

    int head = 0;

    Stiva[ ++head ] = AB[1];
    Stiva[ ++head ] = AB[2];

    for ( int i = 3; i <= NM; ++i )
    {
        while ( head >= 2 && CP( Stiva[head - 1], Stiva[head], AB[i] ) > 0.0f ) head--;

        Stiva[ ++head ] = AB[i];
    }

    for ( int i = head; i >= 1; i-- )
            Polygon[ ++NP ] = Stiva[i];
}

int main()
{
    ifstream f("arie.in");
    ofstream g("arie.out");

    read( f, A, N );
    read( f, B, M );

    compute_areas();
    make_intersection();

    ///cout << NM << endl;

    ///for ( int i = 1; i <= NM; ++i )
            ///cout << AB[i] << endl;

    ///cout << endl;

    ///Segment S( Point( -2, -2 ), Point( 2, -2 ) );

    ///cout << S.contains( Point( 5, -2 ) );

    GrahamScan();

    ///cout << NP << "\n";

    ///for ( int i = 1; i <= NP; ++i )
          ///  cout << Polygon[i] << endl;

    Polygon[NP + 1] = Polygon[1];

    long double area_ch = 0;

    for ( int i = 2; i < NP; ++i )
    {
        area_ch += abs( CP( Polygon[1], Polygon[i], Polygon[i + 1] ) );
    }

    area_ch /= 2.0;

    long double rounded = ( (int)( area_ch * 1000.0f + 0.50000f ) / 1000.0f );

    g << fixed << setprecision( 3 );
    g << rounded << endl;

    ///Segment L1( Point( 1.5, -1.62 ), Point( 5.36, 2.42 ) );
    ///Segment L2( Point( 7.16, -1.84 ), Point( 4.1, 3.8 ) );

    ///Line L1( Point( 6.0, 0.0 ), Point( 1.0, 0.0 ) );
    ///Line L2( Point( 6.0, 2.58 ), Point( -2.0, 2.58 ) );

    ///cout << endl;

    ///cout << L1.intersection( L2 );*/

    return 0;
}