Pagini recente » Rezultatele filtrării | Borderou de evaluare (job #53571) | Cod sursa (job #2266377)
#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-5;
const double pi = acos(-1);
const int MAXN = 512;
inline double get_ang(double ang) {
return ang * 180.0 / pi;
}
inline double get_slope(double s) {
if(s < 0)
return s + 2 * pi;
return s;
}
inline bool ok(double ang, pair <double, double> s) {
if(s.first - s.second < 0) {
return s.first - ang <= 0 && s.second - ang >= 0;
}
else {
return s.first - ang <= 0 || s.second - ang >= 0;
}
}
inline int ccw(int x1, int y1, int x2, int y2, int x3, int y3) {
return x1 * y2 + x2 * y3 + x3 * y1 - y2 * x3 - y3 * x1 - y1 * x2;
}
pair <double, double> seg[MAXN];
double slope[2 * MAXN], arr[2 * MAXN];
bool sol[2 * MAXN];
bitset < 2 * MAXN + 1 > eqs[MAXN];
int main() {
ifstream cin("laser.in");
ofstream cout("laser.out");
int i, j, n;
ios::sync_with_stdio(false);
cin >> n;
int m = 0;
for(i = 0; i < n; i++) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
double ang1 = get_ang(get_slope(atan2(y1, x1))), ang2 = get_ang(get_slope(atan2(y2, x2)));
ang1 *= 1e4;
ang2 *= 1e4;
if(ccw(0, 0, x1, y1, x2, y2) >= 0) {
seg[i] = {ang1, ang2};
}
else {
seg[i] = {ang2, ang1};
}
slope[m++] = ang1;
slope[m++] = ang2;
}
sort(slope, slope + m);
for(i = 0; i < m; i++) {
arr[i] = (slope[i] + slope[(i + 1) % m]) * 0.5;
for(j = 0; j < n; j++) {
if(ok(arr[i], seg[j])) {
eqs[j][i] = 1;
}
}
}
for(i = 0; i < n; i++) {
int x;
cin >> x;
eqs[i][m] = x;
}
int l = 0, c = 0;
while(l < n && c < m) {
i = l;
while(i < n && eqs[i][c] == 0) {
i++;
}
if(i == n) {
c++;
}
else {
swap(eqs[i], eqs[l]);
for(i = l + 1; i < n; i++) {
if(eqs[i][c] == 1)
eqs[i] ^= eqs[l];
}
l++;
c++;
}
}
int cnt = 0;
for(i = n - 1; i >= 0; i--) {
j = 0;
while(j < m && eqs[i][j] == 0) {
j++;
}
for(int p = j + 1; p < m; p++) {
if(eqs[i][p])
eqs[i][m] = eqs[i][m] ^ sol[p];
}
sol[j] = eqs[i][m];
cnt += sol[j];
}
cout << cnt << "\n";
for(i = 0; i < m; i++) {
if(sol[i])
cout << fixed << setprecision(6) << arr[i] / 1e4 << "\n";
}
cin.close();
cout.close();
return 0;
}