Cod sursa(job #1826067)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 10 decembrie 2016 00:56:09
Problema Laser Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.93 kb
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 520;
const double PI = acos(-1.0);

int n;
int x[2 * NMAX];
int y[2 * NMAX];
int idSorted[2 * NMAX];
bitset <2 * NMAX> Sys[NMAX];

inline int crossProduct(int i, int j, int k) {
    int fi = (x[j] - x[i]) * (y[k] - y[i]);
    int se = (x[k] - x[i]) * (y[j] - y[i]);
    return (fi == se ? 0 : (fi < se ? -1 : 1));
}

void rowEchelon() {
    int i = 0;
    int j = 0;
    while (i < n && j < 2 * n) {
        int k = i;
        while (k < n && Sys[k][j] == 0) {
            k++;
        }
        if (k < n) {
            swap(Sys[k], Sys[i]);
            for (k++; k < n; k++) {
                if (Sys[k][j] == 1) {
                    Sys[k] ^= Sys[i];
                }
            }
            i++;
        }
        else {
            j++;
        }
    }
}

vector <bool> Solve() {
    rowEchelon();
    vector <bool> S(2 * n, false);
    vector <bool> Assign(2 * n, false);
    for (int i = n - 1; i >= 0; i--) {
        int p = 0;
        while (p < 2 * n && Sys[i][p] == 0) {
            p++;
        }
        if (p < 2 * n) {
            for (int j = 2 * n - 1; j > p; j--) {
                if (Sys[i][j] == 1) {
                    if (Assign[j] == false) {
                        S[j] = false;
                        Assign[j] = true;
                    }
                    else {
                        Sys[i][2 * n] = Sys[i][2 * n] ^ S[j];
                    }
                }
            }
            Assign[p] = true;
            S[p] = Sys[i][2 * n];
        }
    }
    return S;
}

double Ang(double x, double y) {
    double a = atan2(y, x);
    return (a * 180 / PI) + (360 * (a < 0));
}

int main() {
    freopen("laser.in", "r", stdin);
    freopen("laser.out", "w", stdout);

    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &x[i * 2], &y[i * 2]);
        scanf("%d %d", &x[i * 2 + 1], &y[i * 2 + 1]);
        idSorted[i * 2] = i * 2;
        idSorted[i * 2 + 1] = i * 2 + 1;
        if (crossProduct(2 * n, 2 * i, 2 * i + 1) < 0) {
            swap(x[2 * i], x[2 * i + 1]);
            swap(y[2 * i], y[2 * i + 1]);
        }
    }

    sort(idSorted, idSorted + 2 * n, [&] (int i, int j) { return atan2(y[i], x[i]) < atan2(y[j], x[j]); });

    for (int i = 0; i < n; i++) {
        int d;
        scanf("%d", &d);
        Sys[i][2 * n] = d;
        for (int j = 0; j < 2 * n; j++) {
            int u = idSorted[j];
            int v = idSorted[(j + 1) % (2 * n)];
            if (crossProduct(2 * n, u, 2 * i) <= 0 && crossProduct(2 * n, v, 2 * i + 1) >= 0) {
                Sys[i][j] = 1;
            }
        }
    }

    vector <bool> S = Solve();
    printf("%d\n", count(begin(S), end(S), true));
    for (int i = 0; i < 2 * n; i++) {
        if (S[i] == true) {
            int u = idSorted[i];
            int v = idSorted[(i + 1) % (2 * n)];
            printf("%.6f\n", Ang((x[u] + x[v]) * 0.5, (y[u] + y[v]) * 0.5));
        }
    }

    return 0;
}