Cod sursa(job #1398101)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 23 martie 2015 23:19:19
Problema Laser Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.06 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <bitset>
#include <cmath>

#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];

point middle (const point a, const point b) {
    return point(a.x + b.x, a.y + b.y);
}

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];

bool intersects (const segment &s0, const segment &s1) {
    lint a0 = s0.y1 - s0.y0, b0 = s0.x0 - s0.x1, c0 = s0.x1 * s0.y0 - s0.x0 * s0.y1;
    lint a1 = s1.y1 - s1.y0, b1 = s1.x0 - s1.x1, c1 = s1.x1 * s1.y0 - s1.x0 * s1.y1;

    if (a0 * b1 == a1 * b0)
        return false;

    double x = (double)(c1 * b0 - c0 * b1) / (a0 * b1 - a1 * b0);
    double y = (double)(c1 * a0 - c0 * a1) / (a1 * b0 - a0 * b1);

    if (s1.x1 > 0 && x < -eps)
        return false;
    else if (s1.x1 < 0 && x > eps)
        return false;

    if (s1.y1 > 0 && y < -eps)
        return false;
    else if (s1.y1 < 0 && y > eps)
        return false;

    return (min(s0.x0, s0.x1) <= x && x <= max(s0.x0, s0.x1) && min(s0.y0, s0.y1) <= y && y <= max(s0.y0, s0.y1));
}

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");
    ofstream cout("laser.out");

    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++) {
        poz ++;
        for (j = 1; j <= n; j++) {
            angle[poz] = (atan2(middle(points[i ? i - 1 : 2 * n + 3], points[i]).y, middle(points[i ? i - 1 : 2 * n + 3], points[i]).x) * 180 / pi);
            if (intersects(v[j], segment(0, 0, middle(points[i ? i - 1 : 2 * n + 3], points[i]).x, middle(points[i ? i - 1 : 2 * n + 3], points[i]).y)))
                sistem[j][poz] = 1;
        }

        poz ++;

        for (j = 1; j <= n; j++) {
            angle[poz] = (atan2(points[i].y, points[i].x) * 180 / pi);
            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;
            }
    }

    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;
}