Cod sursa(job #1992728)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 21 iunie 2017 11:33:37
Problema Laser Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.59 kb
#include <fstream>
#include <bitset>
#include <cmath>
#include <algorithm>
#include <iomanip>

using namespace std;

ifstream fin ("laser.in"); ofstream fout ("laser.out");

const int nmax = 512;
const int nrdr = 2 * nmax + 1;
const double eps = 0.00001;
const double pi = acos(-1);

int n, m, cate;
bool st[nmax + 1], sol[nmax + 1];
double u[nrdr + 1];
bitset <nrdr + 2> e[nmax + 1];

struct pct {
    int x, y;
};

struct segm {
    pct a, b;
} v[nmax + 1];

inline void baga_dr (pct a) {
    u[ m ++ ] = atan2(a.y, a.x);
}

bool intersect (segm s, double x) {
    double u1, u2;
    u1 = atan2(s.a.y, s.a.x);
    u2 = atan2(s.b.y, s.b.x);
    if (u1 > u2) swap(u1, u2);

    return (u1 - x < eps && -eps < u2 - x);
}

void simplifica (int x, int y) {
    for (int i = x + 1; i <= n; ++ i) {
        if (e[ i ][ y ] == 1)
            e[ i ] ^= e[ x ];
    }
}

void gauss() {
    int ind = 0;
    for (int i = 1; i <= n; ++ i) {
        int lin;
        while (ind < m) {
            lin = i;
            while (lin <= n && e[ lin ][ ind ] == 0) {
                ++ lin;
            }

            if (lin <= n) {
                break;
            } else {
                ++ ind;
            }
        }

        if (ind < m) {
            swap(e[ i ], e[ lin ]);
            simplifica(i, ind);
        }
    }

    for (int i = n; i > 0; -- i) {
        int pos = -1;
        for (int j = 0; j < m; ++ j) {
            if (e[ i ][ j ] == 1) {
                pos = j; break;
            }
        }

        if (pos != -1) {
            sol[ pos ] = e[ i ][ m ];
            for (int j = pos + 1; j < m; ++ j) {
                sol[ pos ] ^= (e[ i ][ j ] * sol[ j ]);
            }
            cate += sol[ pos ];
        }
    }
}

int main() {
    fin >> n;
    for (int i = 1; i <= n; ++ i) {
        fin >> v[ i ].a.x >> v[ i ].a.y >> v[ i ].b.x >> v[ i ].b.y;
        baga_dr(v[ i ].a);
        baga_dr(v[ i ].b);
    }

    sort(u, u + m);

    for (int i = 0; i < m; ++ i) {
        u[ i ] += eps;
        if (u[ i ] >= 2 * pi) u[ i ] -= 2 * pi;
    }

    for (int j = 1; j <= n; ++ j) {
        for (int i = 0; i < m; ++ i) {
            if (intersect(v[ j ], u[ i ])) {
                e[ j ][ i ] = 1;
            }
        }
        bool aux;
        fin >> aux;
        e[ j ][ m ] = aux;
    }

    gauss();

    fout << cate << "\n";
    fout << setprecision( 8 ) << fixed;

    for (int i = 0; i < m; ++ i) {
        if (sol[ i ] == 1) {
            double unghi = u[ i ] * 180 / pi;
            if (unghi < 0) unghi += 360;
            fout << unghi << "\n";
        }
    }

    fin.close();
    fout.close();
    return 0;
}