Cod sursa(job #1694701)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 25 aprilie 2016 20:08:00
Problema Laser Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.57 kb
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#include <bitset>
using namespace std;
const int NMAX = 553;
const int LMAX = 2055;
const double MIN_ANGLE = 0;
const double MAX_ANGLE = 360.0;
const double EPS = 1e-6;
const double MAX_COORD = 20000;
struct pt {
    double x, y;

    pt operator - (const pt& other) const {
        return {x - other.x, y - other.y};
    }
};

struct segment {
    pt a, b;
    double fromAngle, toAngle;
};

int N, M, state[NMAX];
segment A[NMAX];
double candidates[LMAX];
bitset<LMAX> G[NMAX], res;

double crossProduct(pt p1, pt p2) {
    return p1.x * p2.y - p2.x * p1.y;
}

double direction(pt& p_i, pt& p_j, pt& p_k) {
    return crossProduct(p_k - p_i, p_j - p_i);
}

bool onSegment(pt& p_i, pt& p_j, pt& p_k) {
    return p_k.x >= min(p_i.x, p_j.x) && p_k.x <= max(p_i.x, p_j.x) &&
        p_k.y >= min(p_i.y, p_j.y) && p_k.y <= max(p_i.y, p_j.y);
}

bool lineIntersectsSegment(double ang, segment& s) {
    double m = tan(ang * M_PI / 180);
    double interestingX = (ang >= 180.0 && ang <= 270.0) ? -MAX_COORD : MAX_COORD; 
    pt otherP = {interestingX, interestingX * m};
    pt origin = {0, 0};
    
    double d1 = direction(origin, otherP, s.a);
    double d2 = direction(origin, otherP, s.b);
    double d3 = direction(s.a, s.b, origin);
    double d4 = direction(s.a, s.b, otherP);

    if (((d1 > 0 && d2 < 0) || (d1 < 0 && d2 > 0)) && 
        ((d3 > 0 && d4 < 0) || (d3 < 0 && d4 > 0))) {
        return true;
    }
    if (d1 == 0 && onSegment(origin, otherP, s.a)) {
        return true;
    }
    if (d2 == 0 && onSegment(origin, otherP, s.b)) {
        return true;
    }
    if (d3 == 0 && onSegment(s.a, s.b, origin)) {
        return true;
    }
    if (d4 == 0 && onSegment(s.a, s.b, otherP)) {
        return true;
    }

    return false;
}

inline double angle(pt& p) {
    double atanV = atan2(p.y, p.x);
    atanV = atanV >= 0 ? atanV : (2 * M_PI + atanV);
    return atanV * MAX_ANGLE / (2 * M_PI); 
}

void read() {
    scanf("%d", &N);
    double x1, y1, x2, y2;
    for (int i = 1; i <= N; i++) {
        scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2);
        A[i] = {{x1, y1}, {x2, y2}};
        A[i].fromAngle = angle(A[i].a);
        A[i].toAngle = angle(A[i].b);
        if (A[i].fromAngle > A[i].toAngle) {
            swap(A[i].fromAngle, A[i].toAngle);
        }
    }

    for (int i = 1; i <= N; i++) {
        scanf("%d", &state[i]);
    }
}

void prepare() {
    vector<double> endPoints;
    for (int i = 1; i <= N; i++) {
        endPoints.push_back(A[i].fromAngle + EPS);
        endPoints.push_back(A[i].toAngle - EPS);
    }
    endPoints.push_back(MIN_ANGLE);
    endPoints.push_back(MAX_ANGLE);

    sort(endPoints.begin(), endPoints.end());
    for (size_t i = 0; i < endPoints.size(); i++) {
        candidates[++M] = endPoints[i];
        if (i < endPoints.size() - 1) {
            candidates[++M] = (endPoints[i] + endPoints[i + 1]) / 2;
        }
    }
    sort(candidates + 1, candidates + M + 1);

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            if (lineIntersectsSegment(candidates[j], A[i])) {
                G[i][j] = 1;
            }
        }
        G[i][M + 1] = state[i];
    }
}

void solve() {
    int i = 1, j = 1;
    while (i <= N) {
        if (!G[i][j]) {
            int replacementLine = -1;
            for (int k = i + 1; k <= N; k++) {
                if (G[k][j]) {
                    replacementLine = k;
                    break ;
                }
            }
            if (replacementLine == -1) {
                j++;
                continue ;
            }
            swap(G[i], G[replacementLine]);
        }

        for (int k = i + 1; k <= N; k++) {
            if (G[k][j]) {
                G[k] ^= G[i];
            }
        }
        i++; j++;
    }

    for (int i = N; i >= 1; i--) {
        if (G[i][M + 1]) {
            for (int j = M; j >= 1; j--) {
                if (G[i][j]) {
                    res[j] = G[i][M + 1];
                    for (int k = i - 1; k >= 1; k--) {
                        if (G[k][j]) {
                            G[k] ^= G[i];
                        }
                    }
                    break ;
                }
            }
        }
    }

    vector<double> sol;
    for (int i = 1; i <= M; i++) {
        if (res[i]) {
            sol.push_back(candidates[i]);
        }
    }

    printf("%d\n", (int)sol.size());
    for (auto& ang: sol) {
        printf("%.10lf\n", ang);
    }
}

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

    read();
    prepare();
    solve();
    return 0;
}