Cod sursa(job #1762666)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 23 septembrie 2016 23:37:32
Problema Laser Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.42 kb
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <bitset>
#include <cassert>
 
#define fi first
#define se second
#define mPair make_pair
 
using namespace std;
 
const int kMaxN = 2 * 550;
const double kPi = acos(-1.0);
 
int n;
pair <bool, pair <pair <int, int>, pair <int, int>>> Segs[kMaxN];
pair <int, int> segEnds[2 * kMaxN];
bitset<kMaxN> Gauss[2 * kMaxN];
bool eqSol[2 * kMaxN];
 
bool trigSort(const pair <int, int> &a, const pair <int, int> &b) {
    return atan2(a.se, a.fi) < atan2(b.se, b.fi);
}
 
void rowEchelon() {
    int i = 1, j = 1;
    while (i <= n and j <= 2 * n) {
        int k = i;
        while (k <= n and Gauss[k][j] == false) {
            k += 1;
        }
        if (k <= n) {
            swap(Gauss[i], Gauss[k]);
            k += 1;
            while (k <= n) {
                if (Gauss[k][j] == true) {
                    Gauss[k] ^= Gauss[i];
                }
                k += 1;
            }
            i += 1;
        }
        j += 1;
    }
}
 
int main() {
    freopen("laser.in", "r", stdin);
    freopen("laser.out", "w", stdout);
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d %d", &segEnds[2 * i - 1].fi, &segEnds[2 * i - 1].se);
        scanf("%d %d", &segEnds[2 * i].fi, &segEnds[2 * i].se);
        Segs[i].se.fi = segEnds[2 * i - 1];
        Segs[i].se.se = segEnds[2 * i];
    }
    for (int i = 1; i <= n; i++) {
        scanf("%d", &Segs[i].fi);
        Gauss[i][2 * n + 1] = Segs[i].fi;
    }
    sort(segEnds + 1, segEnds + 2 * n + 1, trigSort);
    for (int i = 1; i <= 2 * n; i++) {
        double xm = (segEnds[i].fi + segEnds[i == 2 * n ? 1 : i + 1].fi) / 2.0;
        double ym = (segEnds[i].se + segEnds[i == 2 * n ? 1 : i + 1].se) / 2.0;
        for (int j = 1; j <= n; j++) {
            double fiSlope = atan2(Segs[j].se.fi.se, Segs[j].se.fi.fi);
            double seSlope = atan2(Segs[j].se.se.se, Segs[j].se.se.fi);
            double mSlope = atan2(ym, xm);
            if (min(fiSlope, seSlope) <= mSlope && mSlope <= max(fiSlope, seSlope)) {
                Gauss[j][i] = true;
            }
        }
    }
    rowEchelon();
//    for (int i = 1; i <= n; i += 1) {
//        for (int j = 1; j <= 2 * n + 1; j += 1) {
//            printf("%d ", (int) Gauss[i][j]);
//        }
//        putchar('\n');
//    }
    for (int i = n; i >= 1; i--) {
        int j = i;
        while (j <= 2 * n and Gauss[i][j] == false) {
            j += 1;
        }
        if (j < 2 * n + 1) {
            eqSol[j] = Gauss[i][2 * n + 1];
            for (int k = j + 1; k <= 2 * n; k += 1) {
                if (Gauss[i][k] == true) {
                    eqSol[j] ^= eqSol[k];
                }
            }
        }
    }
    vector <double> Shoot;
    for (int i = 1; i <= 2 * n; i++) {
        if (eqSol[i] == true) {
            double xm = (segEnds[i].fi + segEnds[i == 2 * n ? 1 : i + 1].fi) / 2.0;
            double ym = (segEnds[i].se + segEnds[i == 2 * n ? 1 : i + 1].se) / 2.0;
            double mSlope = atan2(ym, xm);
            while (mSlope < 0) mSlope += 2 * kPi;
            //printf("%d || %d %d %f %f -> %f\n", i, segEnds[i].fi, segEnds[i == 2 * n ? 1 : i + 1].fi, xm, ym, mSlope);
            Shoot.push_back(mSlope * 180 / kPi);
        }
    }
    printf("%u\n", Shoot.size());
    for (const double x: Shoot) {
        printf("%.15f\n", x);
    }
    return 0;
}