Cod sursa(job #2138365)

Utilizator robx12lnLinca Robert robx12ln Data 21 februarie 2018 16:28:17
Problema Laser Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.69 kb
#include<bits/stdc++.h>
using namespace std;
ifstream fin("laser.in");
ofstream fout("laser.out");
int N, M, i, j, Sol[1030], Nr;
const double PI = 3.14159265;
const double EPS = 1e-6;
struct segm{
    int x1, y1, x2, y2;
} V[520];
pair<int,int> P[520];
bitset<1030> S[520];
inline long long det( pair<int,int> S1, pair<int,int> S2, pair<int,int> P ){
    return 1LL * ( S2.first - S1.first ) * ( P.second - S1.second ) -
           1LL * ( P.first - S1.first ) * ( S2.second - S1.second );
}
inline double get_angle( pair<int, int> P ){
    double x = 1.0 * P.first;
    double y = 1.0 * P.second;
    double alfa = atan2( y, x );
    if( alfa < EPS )
        alfa = alfa + 2 * PI;
    return alfa;
}
inline int Compare( pair<int,int> P1, pair<int,int> P2 ){
    return det( {0, 0}, P1, P2 ) < EPS;
}
int main(){
    fin >> N;
    for( int i = 1; i <= N; i++ ){
        fin >> V[i].x1 >> V[i].y1 >> V[i].x2 >> V[i].y2;
        P[++M] = { V[i].x1, V[i].y1 };
        P[++M] = { V[i].x2, V[i].y2 };
    }
    sort( P + 1, P + M + 1, Compare );
    for( int i = 1; i <= M; i++ ){
        for( int j = 1; j <= N; j++ ){
            if( (P[i].first == V[j].x1 && P[i].second == V[j].y1) || (P[i].first == V[j].x2 && P[i].second == V[j].y2) ){
                S[j][i] = 1;
                continue;
            }
            if( 1LL * det( {0, 0}, P[i], { V[j].x1, V[j].y1 } ) * det( {0, 0}, P[i], { V[j].x2, V[j].y2 } ) < EPS )
                if( 1LL * det( { V[j].x1, V[j].y1 }, { V[j].x2, V[j].y1 }, {0, 0} ) * det( { V[j].x1, V[j].y1 }, { V[j].x2, V[j].y1 }, P[i] ) < EPS )
                    S[j][i] = 1;
        }
    }
    for( int i = 1; i <= N; i++ ){
        int x; fin >> x;
        if( x == 1 )
            S[i][M + 1] = 1;
    }
    for( int i = 1, j = 1; i <= N && j <= M; j++ ){
        for( int ii = i; ii <= N; ii++ ){
            if( S[ii][j] == 1 && ii != i ){
                swap( S[ii], S[i] );
                break;
            }
        }
        if( S[i][j] == 0 )
            continue;
        for( int ii = i + 1; ii <= N; ii++ )
            if( S[ii][j] == 1 )
                S[ii] ^= S[i];
        i++;
    }
    for( int i = N; i >= 1; i-- ){
        int j;
        for( j = 1; j <= M; j++ )
            if( S[i][j] == 1 )
                break;
        if( j <= M )
            Sol[j] = S[i][M + 1];
        for( int ii = j + 1; ii <= M; ii++ )
            Sol[j] = Sol[j] ^ ( Sol[ii] * S[i][ii] );
        Nr += Sol[j];
    }
    fout << Nr << "\n";
    for( int i = 1; i <= M; i++ ){
        if( Sol[i] == 0 )
            continue;
        fout << setprecision(6) << fixed << get_angle( P[i] ) / PI * 180.0 << "\n";
    }
    return 0;
}