Cod sursa(job #2472090)

Utilizator Vlad.Vlad Cristian Vlad. Data 12 octombrie 2019 01:16:25
Problema Laser Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.92 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()]) * 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;
}