Cod sursa(job #2491515)

Utilizator Vlad.Vlad Cristian Vlad. Data 12 noiembrie 2019 18:14:53
Problema Laser Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.82 kb
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <bitset>
#include <iostream>
#include <iomanip>
using namespace std;
ifstream fin("laser.in");
ofstream fout("laser.out");
#define PI 3.14159265358979323846264338327950288
#define EPS 0.000000000000001
struct segment {

    double u1, u2;

};
int n, m;
bitset<520> bits[520];
vector<double> unghiuri;
segment v[520];
int x[520];
bool intersects(segment s, double slope) {
    if (s.u2 - s.u1 > PI)
        return (slope < s.u1 + EPS) || (slope > s.u2 - EPS);
    return (slope - s.u1 > -EPS) && (s.u2 - slope > -EPS);

}
double getSlope(int x, int y) {
    double ata = atan2(y, x);
    if (ata < 0)
        return ata + 2 * PI;
    return ata;

}

vector<double> getShootAngles() {
    vector<double> d;
    sort(unghiuri.begin(), unghiuri.end());
    for (int i = 0; i < unghiuri.size() - 1; ++i) {
        d.push_back((unghiuri[i] + unghiuri[i + 1]) * 0.5);
    }
    d.push_back((unghiuri[0] + unghiuri[unghiuri.size() - 1]) * 0.5);
    return d;
}

void citire() {
    fin >> n;
    for (int i = 0; i < n; ++i) {
        int x1, x2, y1, y2;
        fin >> x1 >> y1 >> x2 >> y2;
        v[i].u1 = getSlope(x1, y1);
        v[i].u2 = getSlope(x2, y2);
        if (v[i].u1 > v[i].u2) {
            swap(v[i].u1, v[i].u2);
        }
        unghiuri.push_back(v[i].u1);
        unghiuri.push_back(v[i].u2);
    }
}

void gaussAlgorithm() {
    int i = 0, j = 0;
    while (i < n && j < m) {
        int iNenul = i;
        while (iNenul < n && !bits[iNenul][j]) {
            iNenul++;
        }
        if (iNenul == n)
            ++j;
        else {
            if (iNenul != i)
                swap(bits[iNenul], bits[i]);
            for (int k = i + 1; k < n; ++k) {
                if (bits[k][j]) {
                    bits[k] = bits[k] ^ bits[i];
                }
            }
            ++i;
            ++j;
        }
    }
}

void getUnknowns() {
    for (int i = n - 1; i >= 0; --i) {
        int jNenul = 0;
        while (jNenul < m && !bits[i][jNenul]) {
            ++jNenul;
        }
        x[jNenul] = bits[i][m];
        for (int j = jNenul + 1; j < m; ++j) {
            x[jNenul] = x[jNenul] ^ (bits[i][j] & x[j]);
        }
    }
}

int main()
{

    citire();
    vector<double> trageri = getShootAngles();
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < trageri.size(); ++j) {
            bits[i][j] = intersects(v[i], trageri[j]);
        }
        bool a;
        fin >> a;
        bits[i][trageri.size()] = a;
    }
    m = trageri.size();
    gaussAlgorithm();
    getUnknowns();
    int con = 0;
    for (int i = 0; i < m; ++i) {
        con += x[i];
    }
    fout << con << "\n";
    for (int i = 0; i < m; ++i) {
        if (x[i])
            fout << fixed << setprecision(8) << trageri[i] * 180 / PI << "\n";
    }
    return 0;

}