Cod sursa(job #1782267)

Utilizator AlexNiuclaeNiculae Alexandru Vlad AlexNiuclae Data 17 octombrie 2016 21:45:44
Problema Laser Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.02 kb
#include <bits/stdc++.h>

#define point pair < double, double >
#define x first
#define y second

using namespace std;

struct segment
{
    double x1, y1, x2, y2;

    segment (double xx1 = 0, double yy1 = 0, double xx2 = 0, double yy2 = 0)
    {
        x1 = xx1; y1 = yy1;
        x2 = xx2; y2 = yy2;
    }
};

const int nmax = 520;
const double PI = acos(-1);
const double eps = 1e-5;

int n;
int idx[nmax];
bool light[nmax], used[nmax];

segment v[nmax];
point ray[nmax<<1];

bitset < nmax << 1 > a[nmax];

int compare(double a, double b)
{
    if (a + eps < b) return -1;
    if (b + eps < a) return 1;
    return 0;
}

int det(point a, point b, point c)
{
    double ret = (a.x - c.x) * (b.y - c.y) - (a.y - c.y) * (b.x - c.x);
    return compare(ret, 0);
}

bool tg_cmp(point a, point b)
{
    return (det(a, b, {0, 0}) == -1);
}

bool intersect(segment a, segment b)
{
    point p1, p2, p3, p4;

    p1 = {a.x1, a.y1}; p2 = {a.x2, a.y2};
    p3 = {b.x1, b.y1}; p4 = {b.x2, b.y2};

    if (det(p1, p2, p3) * det(p1, p2, p4) >= 0)
        return 0;
    if (det(p3, p4, p1) * det(p3, p4, p2) >= 0)
        return 0;

    return 1;
}

void read_input()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
    {
        scanf("%lf %lf", &v[i].x1, &v[i].y1);
        scanf("%lf %lf", &v[i].x2, &v[i].y2);
    }

    for (int i = 1; i <= n; ++i)
        scanf("%d", &light[i]);
}

int prepare_gauss()
{
    int i, j, nr_r = 0;

    for (i = 1; i <= n; ++i)
    {
        ray[++nr_r] = {v[i].x1, v[i].y1};
        ray[++nr_r] = {v[i].x2, v[i].y2};
    }

    sort(ray + 1, ray + nr_r + 1, tg_cmp);
    ray[nr_r+1] = ray[1];

    for (i = 1; i <= nr_r; ++i)
        ray[i].x = (ray[i].x + ray[i+1].x) / 2,
        ray[i].y = (ray[i].y + ray[i+1].y) / 2;

    for (i = 1; i <= n; ++i)
    {
        for (j = 1; j <= nr_r; ++j)
            if (intersect(v[i], segment(0, 0, ray[j].x, ray[j].y)))
                a[i][j] = 1;

        a[i][nr_r+1] = light[i];
    }

    return nr_r;
}

void run_gauss(int n, int m)
{
    for (int i = 1; i <= n; ++i)
    {
        int p = 0;
        for (int j = 1; j <= m + 1 && !p; ++j)
            if (a[i][j] == 1) p = j;

        if (p == 0)
            continue;

        idx[i] = p;
        for (int k = 1; k <= n; ++k)
        {
            if (k == i || !a[k][p]) continue;
            a[k] ^= a[i];
        }
    }

    int ans = 0;
    for (int i = 1; i <= n; ++i)
        if (a[i][m+1]) used[idx[i]] = 1;

    for (int i = 1; i <= m; ++i)
        ans += used[i];

    printf("%d\n", ans);
    for (int i = 1; i <= m; ++i)
    {
        if (!used[i]) continue;

        double angle = atan2(ray[i].y, ray[i].x) * 180 / PI;
        if (compare(angle, 0) == -1) angle += 360;

        printf("%.8f\n", angle);
    }
}

int main()
{
    freopen("laser.in","r",stdin);
    freopen("laser.out","w",stdout);

    read_input();
    int M = prepare_gauss();
    run_gauss(n, M);

    return 0;
}