Cod sursa(job #2921333)

Utilizator lolismekAlex Jerpelea lolismek Data 30 august 2022 12:34:23
Problema Laser Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.66 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>

using namespace std;

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

const int N = 2000;
const double eps = 1e-9, PI = 3.14159265;
vector <double> angles, b;

pair <double, double> interv[N + 1];
bool coef[N + 1][N + 1];
int poz[N + 1];

bool notNull(double x){
    return (x < -eps || x > eps);
}

double angle(double x, double y){
    double ans = atan2(y, x);
    if(ans >= 0)
        return ans;
    else
        return ans + 2 * PI;
    return ans;
}

int main(){

    int n;
    fin >> n;

    for(int i = 1; i <= n; i++){
        int x1, y1, x2, y2;
        fin >> x1 >> y1 >> x2 >> y2;

        double u1 = angle(x1, y1);
        double u2 = angle(x2, y2);

        angles.push_back(u1);
        angles.push_back(u2);

        if(u1 - u2 > eps)
            swap(u1, u2);

        interv[i] = {u1, u2};
    }

    sort(angles.begin(), angles.end());

    for(int i = 0; i < (int)angles.size() - 1; i++)
        b.push_back((angles[i] + angles[i + 1]) / 2);
    b.push_back((angles[(int)angles.size() - 1] + angles[0] + 2 * PI) / 2);
    if(b[(int)b.size() - 1] > 2 * PI)
        b[(int)b.size() - 1] -= 2 * PI;

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= (int)angles.size(); j++){
            bool ok = false;
            if(interv[i].second - interv[i].first > PI)
                ok = ((angles[j - 1] < interv[i].first + eps) || (angles[j - 1] > interv[i].second - eps));
            else
                ok = ((angles[j - 1] - interv[i].first > -eps) && (interv[i].second - angles[j - 1] > -eps));

            coef[i][j] = ok;
        }

    for(int i = 1; i <= n; i++){
        bool touch;
        fin >> touch, coef[i][(int)angles.size() + 1] = touch;
    }

    for(int i = 1; i <= n; i++){
        int j;
        for(j = 1; j <= (int)angles.size() + 1; j++)
            if(coef[i][j])
                break;

        if(j != (int)angles.size() + 2){
            poz[i] = j;
            for(int ind = 1; ind <= n; ind++)
                if(ind != i && coef[ind][poz[i]] != 0)
                    for(int jj = 1; jj <= (int)angles.size() + 1; jj++)
                        coef[ind][jj] ^= coef[i][jj];
        }
    }
        
    vector <double> sol;
    for(int i = 1; i <= n; i++)
        if(poz[i] && coef[i][(int)angles.size() + 1])
            sol.push_back(b[poz[i] - 1]);

    fout << (int)sol.size() << '\n';

    fout << fixed << setprecision(6);

    for(int i = 0; i < (int)sol.size(); i++)
        fout << sol[i] / PI * 180 << '\n';

    return 0;
}