Cod sursa(job #2062457)

Utilizator retrogradLucian Bicsi retrograd Data 10 noiembrie 2017 14:19:12
Problema Laser Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.76 kb
#include <bits/stdc++.h>

using namespace std;

struct TwoSat {
    int n;
    vector<vector<int>> G;
    vector<int> values; // 0 = false, 1 = true

    TwoSat(int n = 0) : n(n), G(2*n) {}

    int AddVar() { // (optional)
        G.emplace_back();
        G.emplace_back();
        return n++;
    }

    void Implies(int a, int b) {
        a = (a >= 0 ? 2*a : -1-2*a);
        b = (b >= 0 ? 2*b : -1-2*b);
        G[a].push_back(b);
    }
    void Either(int a, int b) {
        Implies(~a, b);
        Implies(~b, a);
    }
    void SetValue(int x) {
        Either(x, x);
    }
    void AtMostOne(const vector<int>& vals) { // (optional)
        if (vals.size() <= 1) return;
        int cur = ~vals[0];
        for (int i = 2; i < (int)vals.size(); ++i) {
            int nxt = AddVar();
            Either(cur, ~vals[i]);
            Either(cur, nxt);
            Either(~vals[i], nxt);
            cur = ~nxt;
        }
        Either(cur, ~vals[1]);
    }

    vector<int> enter, comp, stk;
    int timer = 0;
    int dfs(int node) {
        int low = enter[node] = ++timer, x;
        stk.push_back(node);

        for (auto vec : G[node]) if (!comp[vec])
            low = min(low, enter[vec] ?: dfs(vec));
        ++timer;
        if (low == enter[node]) do {
            x = stk.back(); stk.pop_back();
            comp[x] = timer;
            if (values[x >> 1] == -1)
                values[x >> 1] = 1 - x & 1;
        } while (x != node);
        return enter[node] = low;
    }

    bool Solve() {
        values.assign(n, -1);
        enter.assign(2 * n, 0); comp = enter;
        for (int i = 0; i < 2 * n; ++i) {
            if (!comp[i])
                dfs(i);
        }
        for (int i = 0; i < n; ++i) {
            if (comp[2 * i] == comp[2 * i + 1])
                return false;
        }
        return true;
    }
};


struct Angle {
    int x, y;
    int t;
    Angle(int x, int y, int t=0) : x(x), y(y), t(t) {}
    Angle operator-(Angle a) const { return {x-a.x, y-a.y, t}; }
    int quad() const {
        assert(x || y);
        if (y < 0) return (x >= 0) + 2;
        if (y > 0) return (x <= 0);
        return (x <= 0) * 2;
    }
    Angle t90() const { return {-y, x, t + (quad() == 3)}; }
    Angle t180() const { return {-x, -y, t + (quad() >= 2)}; }
    Angle t360() const { return {x, y, t + 1}; }
};
bool operator<(Angle a, Angle b) {
    return make_tuple(a.t, a.quad(), 1LL * a.y * b.x) <
        make_tuple(b.t, b.quad(), 1LL * a.x * b.y);
}
bool operator==(Angle a, Angle b) {
    if (a < b) return false;
    if (b < a) return false;
    return true;
}

pair<Angle, Angle> SegmentAngles(Angle a, Angle b) {
    if (b < a) swap(a, b);
    return (b < a.t180() ?
            make_pair(a, b) : make_pair(b, a.t360()));
}

Angle operator+(Angle a, Angle b) { // where b is a vector
    Angle r(a.x + b.x, a.y + b.y, a.t);
    if (a.t180() < r) r.t--;
    return r.t180() < a ? r.t360() : r;
}

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

    int n; cin >> n;

    vector<Angle> angles;
    vector<pair<Angle, Angle>> seg_angles;

    for (int i = 0; i < n; ++i) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        Angle a1(x1, y1);
        Angle a2(x2, y2);

        auto p = SegmentAngles(a1, a2);
        seg_angles.push_back(p);
        angles.push_back(a1);
        angles.push_back(a2);
    }

    sort(angles.begin(), angles.end());
    angles.erase(unique(angles.begin(), angles.end()), angles.end());

    auto get_norm = [&](Angle a) {
        a.t = 0;
        auto it = lower_bound(angles.begin(), angles.end(), a);
        return distance(angles.begin(), it);
    };

    vector<pair<int, int>> segs;
    for (auto p : seg_angles) {
        int a = get_norm(p.first);
        int b = get_norm(p.second);
        segs.emplace_back(a, b);
    }

    vector<int> initial(n);
    for (int i = 0; i < n; ++i)
        cin >> initial[i];
/*
    for (auto x : angles) {
        cerr << x.x << " " << x.y << "\t";
    }
    cerr << endl;
*/
    for (int s = 0; s < 2; ++s) {
        TwoSat sat(angles.size() + 1);
        sat.SetValue(~0);
        if (!s) sat.SetValue(~angles.size());
        else sat.SetValue(angles.size());

        for (int i = 0; i < n; ++i) {
            int a, b;
            tie(a, b) = segs[i];
            int need = initial[i];
            
            //cerr << "SEGM " << a << " " << b << endl;            
            bool should_eq = (need == (a <= b ? 0 : s));
            if (should_eq) {
                //cerr << a << " == " << b + 1 << endl;
                sat.Implies(a, b + 1);
                sat.Implies(b + 1, a);
                sat.Implies(~a, ~(b + 1));
                sat.Implies(~(b + 1), ~a);
            } else {
                //cerr << a << " != " << b + 1 << endl;
                sat.Implies(a, ~(b + 1));
                sat.Implies(~a, b + 1);
                sat.Implies(~(b + 1), a);
                sat.Implies(b + 1, ~a);
            }
        }

        if (sat.Solve()) {
            int s = 0;
            vector<double> ans;/*
            for (auto x : sat.values)
                cerr << x;
            cerr << endl;*/
            for (int i = 0; i <= (int)angles.size(); ++i) {
                if (sat.values[i] != s) {
                    //cerr << angles[i - 1].x << " " << angles[i - 1].y << endl;
                    ans.push_back(atan2(angles[i - 1].y, angles[i - 1].x));
                    s ^= 1;
                }
            }

            const double kPi = 4.0 * atan(1.0);
            
            cout << ans.size() << '\n';
            cout << fixed << setprecision(20);
            for (auto x : ans) {
                double ret = x / 2 / kPi * 360;
                if (ret < -1e-9) ret += 360;
                cout << ret << '\n';
            }
            return 0;
        }
    }
    
    return 0;
}