Cod sursa(job #2062498)

Utilizator freak93Adrian Budau freak93 Data 10 noiembrie 2017 15:36:16
Problema Laser Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.22 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>

using namespace std;

double to_degrees(double radians) {
     double degrees = radians / (2 * M_PI) * 360;
     if (degrees < 0)
         degrees += 360;
     return degrees;
}

class SatSolver {
  public:
    SatSolver(int size):
        m_edges(size),
        m_value(size, -1),
        m_ok(true) {}

    void setValue(int node, bool value) {
        if (m_value[node] != value && m_value[node] != -1)
            m_ok = false;
        m_value[node] = value;
    }

    void addRestriction(int node1, int node2, bool sum) {
        m_edges[node1].emplace_back(node2, sum);
        m_edges[node2].emplace_back(node1, sum);
    }

    bool value(int node) const {
        return m_value[node];
    }

    int size() const {
        return m_edges.size();
    }

    bool solve() {
        if (!m_ok)
            return false;
        for (int i = 0; i < size(); ++i)
            if (m_value[i] != -1)
                if (!dfs(i))
                    return false;
        for (int i = 0; i < size(); ++i)
            if (m_value[i] == -1) {
                m_value[i] = 0;
                if (!dfs(i))
                    return false;
            }
        return true;
    }
  private:
    bool dfs(int node) {
        for (auto &edge : m_edges[node])
            if (m_value[edge.first] != -1 && m_value[edge.first] != (m_value[node] ^ edge.second))
                return false;
        for (auto &edge : m_edges[node])
            if (m_value[edge.first] == -1) {
                m_value[edge.first] = m_value[node] ^ edge.second;
                if (!dfs(edge.first))
                    return false;
            }
        return true;
    }

    vector< vector< pair<int, int> > > m_edges;
    vector<int> m_value;
    bool m_ok;
};

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

    int N; cin >> N;
    vector< pair<double, double> > intervals;
    for (int i = 0; i < N; ++i) {
        int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
        double start = to_degrees(atan2(y1, x1));
        double end = to_degrees(atan2(y2, x2));
        if (start > end)
            swap(start, end);
        if (end - start > 180)
            intervals.emplace_back(end, start);
        else
            intervals.emplace_back(start, end);
    }

    vector<int> values(N);
    for (int i = 0; i < N; ++i)
        cin >> values[i];

    // normalize
    vector<double> ends;
    for (auto &i : intervals) {
        ends.push_back(i.first);
        ends.push_back(i.second);
    }

    sort(ends.begin(), ends.end());

    vector<double> middle(ends.size());
    for (int i = 0; i < int(middle.size()); ++i)
        middle[i] = (ends[i] + ends[(i + 1) % ends.size()]) / 2;

    vector< pair<int, int> > normalized_intervals;
    for (int i = 0; i < N; ++i) {
        int from = lower_bound(ends.begin(), ends.end(), intervals[i].first) - ends.begin();
        int to = lower_bound(ends.begin(), ends.end(), intervals[i].second) - ends.begin();
        normalized_intervals.emplace_back(from, to);
    }

    for (int total = 0; total < 2; ++total) { // fix the xor of all
        SatSolver S(middle.size());
        S.setValue(middle.size() - 1, total);
        for (int i = 0; i < N; ++i) {
            int from, to;
            tie(from, to) = normalized_intervals[i];
            if (from < to) { // a substring of 1's in gauss
                if (from == 0)
                    S.setValue(to - 1, values[i]);
                else
                    S.addRestriction(from - 1, to - 1, values[i]);
            } else {
                if (to == 0)
                    S.addRestriction(from - 1, middle.size() - 1, values[i]);
                else
                    S.addRestriction(to, from - 1, values[i] ^ total);
            }
        }
        if (S.solve()) {
            vector<double> answer;
            for (int i = 0; i < int(middle.size()); ++i) {
                int value = S.value(i);
                if (i > 0)
                    value ^= S.value(i - 1);
                if (value)
                    answer.push_back(middle[i]);
            }

            cout << answer.size() << "\n";
            for (auto &x : answer)
                cout << x << "\n";
            return 0;
        }
    }
}