Cod sursa(job #1994913)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 26 iunie 2017 16:34:13
Problema Laser Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.09 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 + 5;
const int nrdr = 2 * nmax + 1;
const double pi = acos(-1);

int n, m, cate;
bool sol[nrdr + 1], viz[nmax + 1];
double u[nrdr + 1];
pair<double, int> dr[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);
}

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 ];
        }
    }
}

void calc_lasere() {
    sort(u, u + m);
    double last = u[m - 1];
    for (int i = 0; i < m; ++ i) {
        double aux = u[ i ];
        u[ i ] = (aux + last) / 2;

        if (i == 0 && last - aux > pi) {
            if (u[ i ] > 0) u[ i ] -= pi;
            else            u[ i ] += pi;
        }

        last = aux;
    }

    sort(u, u + m); sort(dr, dr + m);

    int j = 0;
    for (int i = 0; i < m; ++ i) {
        while (j < m && dr[ j ].first < u[ i ]) {
            if (dr[ j ].second < 0) viz[ -dr[ j ].second ] = 0;
            else                    viz[ dr[ j ].second ] = 1;
            ++ j;
        }

        for (int k = 1; k <= n; ++ k) {
            e[ k ][ i ] = viz[ k ];
        }
    }
}

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);

        double u1 = u[m - 2], u2 = u[m - 1];
        if (u1 > u2) swap(u1, u2);
        if (u2 - u1 > pi) {
            swap(u1, u2);
            viz[ i ] = 1;
        }

        dr[m - 2] = make_pair(u1, i);
        dr[m - 1] = make_pair(u2, -i);
    }

    for (int i = 1; i <= n; ++ i) {
        bool aux; fin >> aux;
        e[ i ][ m ] = aux;
    }

    calc_lasere();
    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;
}