Cod sursa(job #2139151)

Utilizator robx12lnLinca Robert robx12ln Data 22 februarie 2018 10:17:17
Problema Laser Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.86 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 ){
    long long D =  1LL * ( S2.first - S1.first ) * ( P.second - S1.second ) -
                   1LL * ( P.first - S1.first ) * ( S2.second - S1.second );
    if( D < 0 )
        return -1;
    if( D > 0 )
        return 1;
    return 0;
}
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.0 * PI;
    return alfa;
}
inline int Compare( pair<int, int> P1, pair<int, int> P2 ){
    return get_angle( P1 ) - get_angle( 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 );
    P[M + 1] = P[1];
    for( int i = 1; i <= M; i++ ){
        pair<int,int> X = { (P[i].first + P[i + 1].first) * 10000, (P[i].second + P[i + 1].second) * 10000 };
        for( int j = 1; j <= N; j++ )
            if( det( {0, 0}, X, { V[j].x1, V[j].y1 } ) * det( {0, 0}, X, { V[j].x2, V[j].y2 } ) < 0 )
                if( det( { V[j].x1, V[j].y1 }, { V[j].x2, V[j].y2 }, {0, 0} ) * det( { V[j].x1, V[j].y1 }, { V[j].x2, V[j].y2 }, X ) < 0 )
                    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; i <= N; i++, fout << "\n" )
        for( int j = 1; j <= M + 1; j++, fout << " " )
            fout << S[i][j];
    */
    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;
}