Cod sursa(job #2283069)

Utilizator Mihai_PredaPreda Mihai Dragos Mihai_Preda Data 14 noiembrie 2018 22:14:58
Problema Laser Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.91 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>

using namespace std;

const double eps = 0.000001;
const double PI = acos(-1);

struct punct
{
    punct(double x = 0, double y = 0)
    {
        this->x = x;
        this->y = y;
    }
    double x, y;
};

struct segm
{
    segm(double x1 = 0, double y1 = 0, double x2 = 0, double y2 = 0)
    {
        this->a.x = x1;
        this->a.y = y1;
        this->b.x = x2;
        this->b.y = y2;
    }
    punct a, b;
    bool aprins;
};

inline double degrees(double radians)
{
    return radians * 180 / PI;
}

inline double GetSlope(const punct &A)
{
    return atan2(A.y, A.x);
}

bool intersect(double slope, const segm &s)
{
    double minSlope = GetSlope(s.a);
    double maxSlope = GetSlope(s.b);
    if(maxSlope < minSlope)
        swap(minSlope, maxSlope);
    return minSlope <= slope && slope <= maxSlope;
}

int main()
{
    ifstream in("laser.in");
    int n;
    in >> n;
    vector<segm> v(n);
    for(auto &s:v)
        in >> s.a.x >> s.a.y >> s.b.x >> s.b.y;
    for(auto &s:v)
        in >> s.aprins;
    in.close();

    int m = 2*n;
    vector<vector<bool> > a(n, vector<bool>(m+1));
    vector<double> slopes(m);
    for(int i = 0; i < n; ++i)
    {
        slopes[2*i] = GetSlope(v[i].a);
        slopes[2*i+1] = GetSlope(v[i].b);
    }
    for(int i = 0; i < n; ++i)
    {
        a[i][m] = v[i].aprins;
        for(int j = 0; j < m; ++j)
        {
            a[i][j] = intersect(slopes[j], v[i]);
          //  cout << degrees(slopes[j]) << " " << v[i].a.x << " " << v[i].a.y << " " << v[i].b.x << " " << v[i].b.y << " " << a[i][j] << "\n";
        }
    }

    for(int i = 0, j = 0; i < n && j < m; ++i, ++j)
    {
        for(int k = i; k < n; ++k)
        {
            if(a[k][j] != 0)
            {
                if(i != k)
                    swap(a[i], a[k]);
                break;
            }
        }

        if(a[i][j] == 0)
        {
            --i;
            continue;
        }

        for(int k = i+1; k < n; ++k)
        {
            for(int l = m; l >= j; --l)
                a[k][l] = a[k][l] ^ (a[i][l] && a[k][j]);
        }
    }

    vector<bool> rasp(m);
    for(int i = n-1; i >= 0; --i)
    {
        int j;
        for(int k = 0; k < m; ++k)
            if(a[i][k] != 0)
            {
                j = k;
                break;
            }
        rasp[j] = a[i][m];
        for(int k = j+1; k < m; ++k)
            rasp[j] = rasp[j] ^ (a[i][k] && rasp[k]);
    }

    ofstream out("laser.out");
    int trageri = 0;
    for(int i = 0; i < m; ++i)
        trageri += rasp[i];
    out << trageri << "\n";
    for(int i = 0; i < m; ++i)
    {
        if(rasp[i])
            out << fixed << setprecision(8) << degrees(slopes[i]) << "\n";
    }
    return 0;
}