Cod sursa(job #1736549)

Utilizator akaprosAna Kapros akapros Data 1 august 2016 23:11:58
Problema Laser Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.38 kb
#include <bits/stdc++.h>
#define maxN 525
#define e 0.00000001
#define inf 1000000000
using namespace std;
int n, m, x[maxN * 2], ans;
bitset < maxN > a[2 * maxN];
struct line
{
    int x, y;
    double d;
} V[2 * maxN];
struct segm
{
    line a, b;
} v[maxN];
void Swap(double &x, double &y)
{
    double aux;
    aux = x;
    x = y;
    y = aux;
}
double degree(line a)
{
    double d = atan2(a.y, a.x) * (180.0 / M_PI);
    if (d < 0.0)
        d += 360.0;
    return d;
}
int cmp(const line a, const line b)
{
    double d1 = degree(a), d2 = degree(b);
    return (d1 < d2);
}
void Gauss()
{
    int i = 1, j = 1;
    while (i <= n && j <= m)
    {
        int x, y;
        for (x = i; x <= n; ++ x)
            if (a[x][j] != 0)
                break;
        if (x == n + 1)
        {
            ++ j;
            continue;
        }
        if (x > i)
            for (y = j; y <= m + 1; ++ y)
            {
                bool bit = a[x][y];
                a[x][y] = a[i][y];
                a[i][y] = bit;
            }

        for (y = i + 1; y <= n; ++ y)
            if (a[y][j] != 0)
                a[y] ^= a[i];
        ++ i;
        ++ j;
        //++ sol;
    }
    //sol = m - sol;
}

void Coef()
{
    int i, j, y;
    for (i = n; i >= 1; -- i)
        for (j = 1; j <= m; ++ j)
            if (a[i][j] != 0)
            {
                /* No solution...
                if (j == m + 1)
                {
                    ans = -1;
                    return ;
                }*/
                x[j] = a[i][m + 1];
                for (y = j + 1; y <= m; ++ y)
                {
                    x[j] -= (a[i][y] != 0) * x[y];
                    if (x[j] < 0)
                        x[j] += 2;
                    if (x[j] >= 2)
                        x[j] -= 2;
                }
                break;
            }
    for (i = 1; i <= m; ++ i)
        if (x[i])
            ++ ans;
}
void read()
{
    int i;
    freopen("laser.in", "r", stdin);
    scanf("%d", &n);
    for (i = 1; i <= n; ++ i)
    {
        scanf("%d %d %d %d", &v[i].a.x, &v[i].a.y, &v[i].b.x, &v[i].b.y);
        V[++ m].x = v[i].a.x;
        V[m].y = v[i].a.y;
        V[++ m].x = v[i].b.x;
        V[m].y = v[i].b.y;
    }
    for (i = 1; i <= n; ++ i)
    {
        bool st = false;
        scanf("%d", &st);
        a[i][m + 1] = st;
    }
}

bool intersects(int i, int j)
{
    double d1 = degree(v[i].a), d2 = degree(v[i].b), d = V[j].d;
    if (d1 > d2)
        Swap(d1, d2);

    if (d2 - d1 < 180.0 + e)
        return (d1 - e <= d && d <= d2 + e);
    return ((d <= d1 + e) || (d >= d2 - e));
}
void solve()
{
    int i, j;
    sort(V + 1, V + m + 1, cmp);
    V[m + 1] = V[1];
    for (i = 1; i <= m; ++ i)
    {
        V[i].d = (degree(V[i]) + degree(V[i + 1]) + 360 * (i == m)) / 2.0;
        if (V[i].d > 360)
            V[i].d -= 360;
    }

    for (i = 1; i <= n; ++ i)
        for (j = 1; j <= m; ++ j)
            if (intersects(i, j))
                a[i][j] = 1;

    printf("\n");
    Gauss();
    Coef();
}
void write()
{
    int i;
    freopen("laser.out", "w", stdout);
    printf("%d\n", ans);

    for (i = 1; i <= m; ++ i)
        if (x[i])
            printf("%.7lf\n", V[i].d);
}
int main()
{
    read();
    solve();
    write();
    return 0;
}