Pagini recente » Cod sursa (job #2541032) | Cod sursa (job #3160159) | Cod sursa (job #115391) | Cod sursa (job #3029952) | Cod sursa (job #2062507)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#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, to - 1, values[i]);
} else {
if (to == 0)
S.addRestriction(from, 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;
}
}
}