Cod sursa(job #1399018)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 24 martie 2015 15:21:11
Problema Laser Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.5 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <bitset>
#include <cmath>
#include <cassert>

#define NMAX 520
#define inf 10005
#define lint long long int
#define eps 0.000001
#define pi 3.14159265358979
using namespace std;

struct point {
    int x, y;

    point (int x = 0, int y = 0): x(x), y(y) {}
} points[2 * NMAX];

inline bool operator< (const point &a, const point &b) {
    return atan2(a.y, a.x) < atan2(b.y, b.x);
}

struct segment {
    int x0, y0, x1, y1;

    segment (int x0 = 0, int y0 = 0, int x1 = 0, int y1 = 0): x0(x0), y0(y0), x1(x1), y1(y1) {}
} v[NMAX];

inline int ccw (const point &a, const point &b, const point &c) {
    return (a.x - b.x) * (c.y - b.y) - (a.y - b.y) * (c.x - b.x);
}

ofstream cout("laser.out");

bool intersects (const segment &s0, segment s1) {
    int aux = inf / max(abs(s1.x1), abs(s1.y1)) + 1;

    s1.x1 *= aux;
    s1.y1 *= aux;

   // cout << s1.x1 << ' ' << s1.y1 << endl;

    assert(abs(s1.x1) >= inf || abs(s1.y1) >= inf);
    assert(abs(s1.x1) <= 2 * inf && abs(s1.y1) <= 2 * inf);

    //if (min(max(s0.x0, s0.x1), max(s1.x0, s1.x1)) < max(min(s0.x0, s0.x1), min(s1.x0, s1.x1)))
    //    return 0;
    //if (min(max(s0.y0, s0.y1), max(s1.y0, s1.y1)) < max(min(s0.y0, s0.y1), min(s1.y0, s1.y1)))
    //    return 0;

    if (max(s0.x0, s0.x1) < min(s1.x0, s1.x1))
        return 0;
    if (max(s1.x0, s1.x1) < min(s0.x0, s0.x1))
        return 0;

    if (max(s0.y0, s0.y1) < min(s1.y0, s1.y1))
        return 0;
    if (max(s1.y0, s1.y1) < min(s0.y0, s0.y1))
        return 0;

    if (1ll * ccw(point(s0.x0, s0.y0), point(s0.x1, s0.y1), point(s1.x0, s1.y0)) *  ccw(point(s0.x0, s0.y0), point(s0.x1, s0.y1), point(s1.x1, s1.y1)) > 0)
        return 0;
    if (1ll * ccw(point(s1.x0, s1.y0), point(s1.x1, s1.y1), point(s0.x0, s0.y0)) *  ccw(point(s1.x0, s1.y0), point(s1.x1, s1.y1), point(s0.x1, s0.y1)) > 0)
        return 0;
    return 1;
}

istream& operator>> (istream &f, segment &x) {
    f >> x.x0 >> x.y0 >> x.x1 >> x.y1;

    return f;
}

bitset <4 * NMAX> sistem[NMAX];
double angle[4 * NMAX];

bitset <4 * NMAX> sol;

int main()
{
    ifstream cin("laser.in");

    int n = 0;
    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> v[i];

        points[2 * i - 1] = point(v[i].x0, v[i].y0);
        points[2 * i] = point(v[i].x1, v[i].y1);
    }

    points[0] = point(-inf, 0);
    points[2 * n + 1] = point(0, -inf);
    points[2 * n + 2] = point(inf, 0);
    points[2 * n + 3] = point(0, inf);

    sort(points + 1, points + 2 * n + 4);

    int poz = -1, j;

    for (int i = 0; i <= 2 * n + 3; i++) {
        angle[++ poz] = (atan2(points[i ? i - 1 : 2 * n + 3].y + points[i].y, points[i ? i - 1 : 2 * n + 3].x + points[i].x) * 180 / pi);

        for (j = 1; j <= n; j++) {
            if (intersects(v[j], segment(0, 0, points[i ? i - 1 : 2 * n + 3].x + points[i].x, points[i ? i - 1 : 2 * n + 3].y + points[i].y)))
                sistem[j][poz] = 1;
        }

        angle[++ poz] = (atan2(points[i].y, points[i].x) * 180 / pi);

        for (j = 1; j <= n; j++) {
            if (intersects(v[j], segment(0, 0, points[i].x, points[i].y)))
                sistem[j][poz] = 1;
        }
    }

    poz ++;

    bool aux;
    for (int i = 1; i <= n; i++) {
        cin >> aux;
        sistem[i][poz] = aux;
    }

    for (int i = 1; i <= poz; i++) {
        if (angle[i] < 0)
            angle[i] = 360 + angle[i];
    }

    //GAUSS
    int m = poz - 1;
    int cine = 1;

    for (int i = 1; i <= m; i++) {
        for (j = cine; j <= n; j++)
            if (sistem[j][i])
                break;

        if (j == (n + 1))
            continue;
        swap(sistem[j], sistem[cine]);

        for (j = cine + 1; j <= n; j++)
            if (sistem[j][i])
                sistem[j] ^= sistem[cine];

        cine ++;
    }

    while (--cine) {
        aux = sistem[cine][m + 1];
        for (j = 1; j <= m; j++)
            if (sistem[cine][j])
                aux ^= sol[j];

        for (j = 1; j <= m; j++)
            if (sistem[cine][j]) {
                sol[j] = aux;

                break;
            }
    }

    //PRINT
    int cate = 0;
    for (int i = 1; i <= m; i++)
        cate += sol[i];

    cout << cate << '\n' << fixed << setprecision(6);
    for (int i = 1; i <= m; i++)
        if (sol[i])
            cout << angle[i] << '\n';

    cin.close();
    cout.close();
    return 0;
}