Cod sursa(job #2081824)

Utilizator nurof3nCioc Alex-Andrei nurof3n Data 5 decembrie 2017 10:59:50
Problema Laser Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.67 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-6;
struct punct
{
    int x, y;
};
struct unghi
{
    double v;
    int capat, i;
} v[513];
int stare[513], A[513][1025], x[1025];
int N, M, nrsol;
double sol[1025];

bool cmp(const unghi a, const unghi b)
{
    return a.v < b.v;
}

double unghi(punct A)
{
    return atan2(A.y, A.x) * 180 / M_PI;
}
void gauss()
{
    int i = 1, j = 1;
    while(i <= N && j <= M)
    {
        if(abs(A[i][j]) < eps)
        {
            bool praf = 0;
            for(int k = i + 1; k <= N; k++)
                if(abs(A[k][j]) > eps) //if(A[j][i] != 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]  < -eps) 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 && abs(A[i][j]) <= eps) 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;
        if(x[j] == 1) nrsol++;
    }
}

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[++M].v = u1, v[M].capat = 1, v[M].i = i;
        v[++M].v = u2, v[M].capat = 2, v[M].i = i;
    }
    for(int i = 1; i <= N; i++)
        f >> stare[i];
    sort(v + 1, v + M + 1, cmp);
    M--;
    for(int i = 1; i <= M; i++)
    {
        if(v[i].capat == 1) A[v[i].i][i] = 1;
        if(v[i + 1].capat == 2) A[v[i + 1].i][i] = 1;
        sol[i] = (v[i].v + v[i + 1].v) / 2; //valoarea unghiului reprezentativ comutatorului
        if(sol[i] < 0) sol[i] += 360;
    }
    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;
}