Cod sursa(job #2087754)

Utilizator nurof3nCioc Alex-Andrei nurof3n Data 14 decembrie 2017 10:02:38
Problema Laser Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.07 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <iomanip>

using namespace std;
ifstream f("laser.in");
ofstream g("laser.out");
const double eps = 1e-8;
struct punct
{
    int x, y;
};
struct unghi
{
    double u1, u2;
} v[520];
int stare[520], A[520][1040], x[1040];
int N, M, nrsol;
double sol[1040], u[1040];

double unghi(punct A)
{
    double u = atan2(A.y, A.x) * 180 / M_PI;
    return u < 0 ? u + 360 : u;
}

void gauss()
{
    int i = 1, j = 1;
    while(i <= N && j <= M)
    {
        if(A[i][j] == 0)
        {
            bool praf = 0;
            for(int k = i + 1; k <= N; k++)
                if(A[k][j] != 0)
                {
                    for(int l = j; l <= M + 1; l++)
                        swap(A[i][l], A[k][l]);
                    praf = 1;
                    break;
                }
            if(praf == 0)
            {
                j++;
                continue;
            }
        }
        for(int l = i + 1; l <= N; l++)
        {
            for(int k = j + 1; k <= M + 1; k++)
            {
                A[l][k] -= A[i][k] * A[l][j] % 2;
                if(A[l][k]  < 0) A[l][k] += 2;
            }
            A[l][j] = 0;
        }
        i++, j++;
    }
}
void detsol()
{
    int j;
    for(int i = N; i >= 1; i--)
    {
        j = 1;
        while(j <= M + 1 && A[i][j] == 0) j++;
        if(j == M + 2) continue;
        x[j] = A[i][M + 1];
        for(int k = j + 1; k <= M; k++)
            x[j] -= A[i][k] * x[k];
        x[j] %= 2;
        if(x[j] < 0) x[j] += 2;
    }
    for(int j = 1; j <= M; j++)
        if(x[j] == 1) nrsol++;
}

void afisare()
{
    for(int i = 1; i <= M; i++)
        cout << u[i] << ' ';
    cout << endl;
}

int main()
{
    punct C, B;
    f >> N;
    for(int i = 1; i <= N; i++)
    {
        f >> C.x >> C.y >> B.x >> B.y;
        double u1, u2;
        u1 = unghi(C), u2 = unghi(B);
        if(u1 > u2) swap(u1, u2);
        v[i].u1 = u1, u[++M] = u1;
        v[i].u2 = u2, u[++M] = u2;
    }
    for(int i = 1; i <= N; i++)
    {
        f >> stare[i];
        if(stare[i] != 1) stare[i] = 0;
    }

    sort(u + 1, u + M + 1);
    int k = 1;
    for(int i = 1; i < M; i++)
        if(u[i] != u[i + 1]) u[++k] = u[i + 1];
    M = k;
    u[M + 1] = 360 - u[1];
    for(int i = 1; i <= M; i++)
    {
        sol[i] = (u[i] + u[i + 1]) / 2; //valoarea unghiului reprezentativ comutatorului
        for(int j = 1; j <= N; j++)
            if(v[j].u2 - v[j].u1 - 180 < -eps)
            {
                if(v[j].u1 - sol[i] < -eps  && v[j].u2 - sol[i] > eps)
                    A[j][i] = 1;
            }
            else
                if(v[j].u1 - sol[i] > eps && v[j].u2 - 360 - sol[i] < eps)
                    A[j][i] = 1;
    }
    for(int i = 1; i <= N; i++)
        A[i][M + 1] = stare[i];
    gauss();
    detsol();
    g << nrsol << '\n';
    for(int i = 1; i <= M; i++)
        if(x[i])
            g << fixed << setprecision(6) << sol[i] << '\n';
    return 0;
}