Pagini recente » Cod sursa (job #2038324) | Cod sursa (job #2519705) | Cod sursa (job #361261) | Cod sursa (job #3182876) | Cod sursa (job #2429100)
#include <bits/stdc++.h>
#define all(cont) cont.begin(), cont.end()
#define pb push_back
#define fi first
#define se second
#define DEBUG(x) cerr << (#x) << ": " << (x) << '\n'
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef long long ll;
typedef unsigned long long ull;
template<class T> bool uin(T &a, T b) {return (a < b ? false : (a = b, true));}
template<class T> bool uax(T &a, T b) {return (a > b ? false : (a = b, true));}
ifstream f("laser.in");
ofstream g("laser.out");
#define double long double
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
#ifdef LOCAL_DEFINE
freopen(".in", "r", stdin);
#endif
const double PI = 3.14159265358979323846264338327950288;
const double EPS = 0.00001;
int n;
f >> n;
vector<pair<double, double>> segm(n);
vector<double> points(2 * n);
for (int i = 0; i < n; ++i) {
auto readAng = [&]() {
int x, y;
f >> x >> y;
double ang = atan2(y, x);
if (ang < 0) { // le bagam in [0, 360]
ang += 2 * PI;
}
return ang;
};
double ang1 = readAng();
double ang2 = readAng();
if (ang1 > ang2) {
swap(ang1, ang2);
}
segm[i] = {ang1, ang2};
points[2 * i] = ang1;
points[2 * i + 1] = ang2;
}
sort(points.begin(), points.end());
auto aux = points;
aux.emplace_back(points[0] + 2 * PI);
for (int i = 0; i < 2 * n; ++i) {
points[i] = (aux[i] + aux[i + 1]) * 0.5;
if (points[i] >= 2 * PI) {
points[i] -= 2 * PI;
}
assert(points[i] >= 0);
}
sort(points.begin(), points.end());
auto intersects = [&](double ang, pair<double, double> segm) {
if (segm.second - segm.first > PI) {
return segm.first + EPS >= ang || ang >= segm.second - EPS;
}
return segm.first - EPS <= ang && ang <= segm.second + EPS;
};
vector<bitset<1025>> gauss(n);
for (int i = 0; i < n; ++i) {
bool state;
f >> state;
gauss[i][2 * n] = state;
for (int j = 0; j < 2 * n; ++j) {
gauss[i][j] = intersects(points[j], segm[i]);
}
}
int i = 0, j = 0;
while (i < n && j < 2 * n + 1) {
int k = i;
while (k < n && !gauss[k][j]) {
++k;
}
if (k == n) {
++j;
continue;
}
if (i != k) {
swap(gauss[i], gauss[k]);
}
for (int row = i + 1; row < n; ++row) {
if (gauss[row][j]) {
gauss[row] ^= gauss[i];
}
}
++i;
++j;
}
int res = 0;
vector<bool> ans(2 * n);
for (int i = n - 1; i >= 0; --i) {
for (int j = 0; j < 2 * n; ++j) {
if (!gauss[i][j]) {
continue;
}
ans[j] = gauss[i][2 * n];
for (int k = j + 1; k < 2 * n; ++k) {
ans[j] = ans[j] ^ (ans[k] & gauss[i][k]);
}
if (ans[j]) {
++res;
}
break;
}
}
g << res << '\n';
g.precision(7);
g << fixed;
for (int i = 0; i < 2 * n; ++i) {
if (ans[i]) {
g << points[i] * 180.0 / PI << '\n';
}
}
f.close();
g.close();
#ifdef LOCAL_DEFINE
cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
return 0;
}