Cod sursa(job #2851359)

Utilizator toma_ariciuAriciu Toma toma_ariciu Data 18 februarie 2022 15:01:09
Problema Laser Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.25 kb
#include <fstream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <iomanip>

using namespace std;

ifstream fin("laser.in");
ofstream fout("laser.out");

const double pi = 3.14159265, eps = 0.0000000001;
const int maxN = 1300;
int n;
int p[maxN + 5];
pair <double, double> v[maxN + 5];
bool mat[maxN + 5][maxN + 5];
vector <double> inter, bisect, ans;

double unghi(double x, double y)
{
    double rasp = atan2(y, x);
    if(rasp < 0)
        rasp += 2 * pi;
    return rasp;
}

bool check(pair <double, double> poz, double x)
{
    if(poz.second - poz.first > pi)
        return (x < poz.first + eps) || (x > poz.second - eps);
    return (x - poz.first > -eps) && (poz.second - x > -eps);
}

int main()
{
    fin >> n;
    for (int i = 1; i <= n; i++)
    {
        int x1, y1, x2, y2;
        fin >> x1 >> y1 >> x2 >> y2;
        double st, dr;
        st = unghi(x1, y1);
        dr = unghi(x2, y2);
        if(st - dr > eps)
            swap(st, dr);
        v[i] = {st, dr};
        inter.push_back(st);
        inter.push_back(dr);
    }

    sort(inter.begin(), inter.end());
    int m = inter.size();
    for(int i = 0; i + 1 < inter.size(); i++)
        bisect.push_back((inter[i] + inter[i + 1]) / 2);
    bisect.push_back((inter[0] + inter[m - 1] + 2 * pi) / 2);
    if(bisect.back() > 2 * pi)
        bisect.back() -= 2 * pi;

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            mat[i][j] = check(v[i], bisect[j - 1]);
    for (int i = 1; i <= n; i++)
    {
        int x;
        fin >> x;
        mat[i][m + 1] = x;
    }
    int i, j;
    for(i = 1; i <= n; i++)
    {
        for(j = 1; j <= m + 1; j++)
            if(mat[i][j])
                break;
        if(j == m + 2)
            continue;
        p[i] = j;
        for(int k = 1; k <= n; k++)
            if(i != k && mat[k][p[i]])
                for(int l = 1; l <= m + 1; l++)
                    mat[k][l] ^= mat[i][l];
    }
    for (int i = 1; i <= n; i++)
        if (p[i] && mat[i][m + 1])
            ans.push_back(bisect[p[i] - 1]);
    fout << ans.size () << '\n';
    for (double elem : ans)
        fout << fixed << setprecision(6) << elem / pi * 180 << '\n';
    return 0;
}