Cod sursa(job #1860476)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 28 ianuarie 2017 08:52:19
Problema Camera Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.6 kb
#include <bits/stdc++.h>
using namespace std;

fstream in ( "camera.in" , ios::in  );
fstream out( "camera.out", ios::out );

typedef pair<long double, long double> pdd;

const int DIM = 2e3 + 9;
const long double INF = 1e5 + 5;

vector<pdd> lst1, lst2, pts;

inline pdd isg( pdd p1, pdd p2, pdd p3, pdd p4 ) {
    long double a1 = p1.second - p2.second, b1 = p2.first - p1.first, c1 = p1.first * p2.second - p1.second * p2.first;
    long double a2 = p3.second - p4.second, b2 = p4.first - p3.first, c2 = p3.first * p4.second - p3.second * p4.first;
    
    return make_pair( ( c2 * b1 - c1 * b2 ) / ( a1 * b2 - a2 * b1 ),
                      ( c2 * a1 - c1 * a2 ) / ( b1 * a2 - b2 * a1 ) );
}

inline long double ccw( pdd p1, pdd p2, pdd p3 ) {
    return ( p2.first - p1.first ) * ( p3.second - p1.second ) -
           ( p3.first - p1.first ) * ( p2.second - p1.second );
}

int main( void ) {
    ios::sync_with_stdio( false );
    
    int n;
    in >> n;
    
    long double arr = 0;
    for( int i = 0; i < n; i ++ ) {
        int x, y;
        in >> x >> y;

        pts.push_back( make_pair( x, y ) );
    }
    pts.push_back( pts.front() );
    
    arr = 0.0;
    for( int i = 0; i + 1 < pts.size(); i ++ )
        arr += ccw( pts[i], pts[i + 1], make_pair( 0.0, 0.0 ) );
    
    if( arr > 0.0 )
        reverse( pts.begin(), pts.end() );
    
    lst1.push_back( make_pair( -INF, -INF ) ); lst1.push_back( make_pair( -INF, +INF ) );
    lst1.push_back( make_pair( +INF, +INF ) ); lst1.push_back( make_pair( +INF, -INF ) );
    
    lst1.push_back( lst1.front() );
    for( int i = 0; i + 1 < pts.size(); i ++ ) {
        for( int j = 0; j + 1 < lst1.size(); j ++ ) {
            if( ccw( pts[i], pts[i + 1], lst1[j] ) * ccw( pts[i], pts[i + 1], lst1[j + 1] ) < 0 ) {
                if( ccw( pts[i], pts[i + 1], lst1[j] ) <= 0.0 ) {
                    lst2.push_back( lst1[j] );
                    lst2.push_back( isg( pts[i], pts[i + 1], lst1[j], lst1[j + 1] ) );
                }
                else {
                    lst2.push_back( isg( pts[i], pts[i + 1], lst1[j], lst1[j + 1] ) );
                    lst2.push_back( lst1[j + 1] );
                }
            }
            else {
                if( ccw( pts[i], pts[i + 1], lst1[j] ) <= 0.0 )
                    lst2.push_back( lst1[j] );
            }
        }
        
        lst1 = lst2; lst2.clear();
        lst1.push_back( lst1.front() );
    }
    
    arr = 0.0;
    for( int i = 0; i + 1 < lst1.size(); i ++ )
        arr += ccw( lst1[i], lst1[i + 1], make_pair( 0.0, 0.0 ) );
    
    out << setprecision(2) << fixed << fabs( arr ) / 2.0 << endl;
    return 0;
}