Cod sursa(job #2592039)

Utilizator andreiomd1Onut Andrei andreiomd1 Data 31 martie 2020 23:26:45
Problema Laser Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.78 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("laser.in");
ofstream g("laser.out");

typedef pair < int, int > PII;
typedef pair < PII, PII > Segment;

const int NMAX = (1 << 9) + 5;
const long double DOI = 2.000000, PI = acos(-1), Q = 180.000000;

int N;
bool State[NMAX];

Segment A[NMAX];

int M = 0;
PII Points[(NMAX << 1)];

int v = 0;
long double V[(NMAX << 1)];

vector < long double > Bisect;

bitset < (NMAX << 1) > G[NMAX];

int Equations = 0, Variables = 0;

int Chosen[NMAX];
bool fr[(NMAX << 1)];

static inline long double GetAngle (int X, int Y)
{
    long double x = X, y = Y;

    long double ans = atan2(y, x);

    if(y < 0)
        ans += DOI * PI;

    return (ans * (Q / PI));
}

static inline void Read ()
{
    f.tie(NULL);

    f >> N;

    for(int i = 1; i <= N; ++i)
    {
        int X1 = 0, Y1 = 0, X2 = 0, Y2 = 0;

        f >> X1 >> Y1 >> X2 >> Y2;

        if(GetAngle(X1, Y1) > GetAngle(X2, Y2))
            swap(X1, X2), swap(Y1, Y2);

        A[i] = {{X1, Y1}, {X2, Y2}};

        Points[++M] = {X1, Y1};
        Points[++M] = {X2, Y2};
    }

    Equations = N;

    return;
}

auto cmp = [] (PII A, PII B)
{
    if(GetAngle(A.first, A.second) < GetAngle(B.first, B.second))
        return 1;

    return 0;
};

static inline void Build ()
{
    sort(Points + 1, Points + M + 1, cmp);

    V[++v] = GetAngle(Points[1].first, Points[1].second);

    for(int i = 2; i <= M; ++i)
    {
        long double Now = GetAngle(Points[i].first, Points[i].second);

        if(Now == V[v])
            continue;

        V[++v] = Now;
    }

    for(int i = 1; i < v; ++i)
        Bisect.push_back((V[i] + V[i + 1]) / DOI);

    if(v > 1)
    {
        Bisect.push_back((V[1] + V[v] + DOI * Q) / DOI);

        if(Bisect.back() > (DOI * Q))
            Bisect.back() -= (DOI * Q);
    }

    Variables = (int)Bisect.size();

    for(int i = 1; i <= N; ++i)
    {
        f >> State[i];

        G[i][Variables + 1] = State[i];
    }

    return;
}

static inline void Continue ()
{
    for(int i = 1; i <= N; ++i)
    {
        long double Min = GetAngle(A[i].first.first, A[i].first.second);
        long double Max = GetAngle(A[i].second.first, A[i].second.second);

        long double Delta = Max - Min;
        bool Val = 0;

        if(Delta > Q)
            Val = 1;

        for(int j = 0; j < Variables; ++j)
        {
            long double Angle = Bisect[j];

            int Bool = 0;

            if(Val == 0)
            {
                if(Angle >= Min && Angle <= Max)
                    Bool = 1;
            }
            else
            {
                if(Angle < Min || Angle > Max)
                    Bool = 1;
            }

            G[i][j + 1] = Bool;
        }
    }

    return;
}

static inline void GaussianElimination ()
{
    for(int i = 1; i <= Equations; ++i)
    {
        int pos = 0;

        for(int j = 1; j <= Variables + 1; ++j)
            if(G[i][j])
            {
                pos = j;

                break;
            }

        if(pos == 0)
            continue;

        Chosen[i] = pos;

        for(int j = 1; j <= Equations; ++j)
            if(i != j && G[j][pos])
                G[j] ^= G[i];
    }

    return;
}

static inline void Write ()
{
    int r = 0;

    for(int i = 1; i <= Equations; ++i)
        if(Chosen[i])
            fr[Chosen[i]] = 1, ++r;

    g << r << '\n';

    g << setprecision(6) << fixed;

    for(int i = 1; i <= Variables; ++i)
        if(fr[i])
            g << Bisect[i - 1] << '\n';

    return;
}

int main()
{
    Read();

    Build();

    Continue();

    GaussianElimination();

    Write();

    return 0;
}