Cod sursa(job #1970040)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 18 aprilie 2017 20:26:38
Problema Laser Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.8 kb
#include <bits/stdc++.h>
using namespace std;

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

const int DIM = 515;

bitset<DIM * 2> sys[DIM], ans;
pair<int, int> seg[DIM * 2], ept1[DIM], ept2[DIM];

inline long long ccw( const pair<int, int> pt1, const pair<int, int> pt2, const pair<int, int> pt3 ) {
    return 1LL * ( pt2.first - pt1.first ) * ( pt3.second - pt1.second ) -
           1LL * ( pt3.first - pt1.first ) * ( pt2.second - pt1.second );
}

inline bool comp( const pair<int, int> pt1, const pair<int, int> pt2 ) {
    return ccw( make_pair( 0, 0 ), pt1, pt2 ) > 0;
}

int main( void ) {
    
    int n, m = 0;
    in >> n;
    
    for( int i = 1; i <= n; i ++ ) {
        in >> ept1[i].first >> ept1[i].second;
        in >> ept2[i].first >> ept2[i].second;
        
        seg[++ m] = make_pair( ept1[i].first, ept1[i].second );
        seg[++ m] = make_pair( ept2[i].first, ept2[i].second );
    }
    
    for( int i = 1; i <= n; i ++ ) {
        bool x;
        in >> x;
        
        sys[i][m + 1] = x;
    }
    
    sort( seg + 1, seg + m + 1, comp );
    
    seg[m + 1] = seg[1];
    for( int i = 1; i <= m; i ++ ) {
        pair<int, int> pt1 = make_pair( 0, 0 );
        pair<int, int> pt2 = make_pair( ( seg[i].first  + seg[i + 1].first  ) * 10000,
                                        ( seg[i].second + seg[i + 1].second ) * 10000 );
        
        for( int j = 1; j <= n; j ++ ) {
            if( ccw( pt1, pt2, ept1[j] ) * ccw( pt1, pt2, ept2[j] ) < 0 )
            if( ccw( ept1[j], ept2[j], pt1 ) * ccw( ept1[j], ept2[j], pt2 ) < 0 )
                sys[j][i] = true;
        }
    }
 
    for( int i = 1, j = 1; i <= n && j <= m; ) {
        bool ok = false;
        
        for( int k = i; k <= n; k ++ ) {
            if( sys[k][j] == true ) {
                swap( sys[i], sys[k] );
                ok = true; break;
            }
        }
        
        if( ok == false )
            j ++;
        else {
            for( int k = i + 1; k <= n; k ++ )
                if( sys[k][j] == true )
                    sys[k] ^= sys[i];
            
            i ++; j ++;
        }
    }
    
    for( int i = n, j = 1; i >= 1; i --, j = 1 ) {
        while( sys[i][j] == false )
            j ++;
        
        ans[j] = sys[i][m + 1];
        for( int p = j + 1; p <= m; p ++ )
            ans[j] = ans[j] ^ ( ans[p] & sys[i][p] );
    }
    
    out << ans.count() << "\n";
    for( int i = 1; i <= m; i ++ ) {
        if( ans[i] == true ) {
            double ang = atan2( ( seg[i].second + seg[i + 1].second ) * 10000,
                                ( seg[i].first  + seg[i + 1].first  ) * 10000 ) * 180 / acos( -1 );
            if( ang < 0 )
                ang += 360;
            
            out << setprecision( 6 ) << fixed << ang << "\n";
        }
    }
    
    return 0;
}