Pagini recente » Cod sursa (job #2869484) | Cod sursa (job #2143587) | Cod sursa (job #238077) | Cod sursa (job #503774) | Cod sursa (job #1994913)
#include <fstream>
#include <bitset>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin ("laser.in"); ofstream fout ("laser.out");
const int nmax = 512 + 5;
const int nrdr = 2 * nmax + 1;
const double pi = acos(-1);
int n, m, cate;
bool sol[nrdr + 1], viz[nmax + 1];
double u[nrdr + 1];
pair<double, int> dr[nrdr + 1];
bitset <nrdr + 2> e[nmax + 1];
struct pct {
int x, y;
};
struct segm {
pct a, b;
} v[nmax + 1];
inline void baga_dr (pct a) {
u[ m ++ ] = atan2(a.y, a.x);
}
void simplifica (int x, int y) {
for (int i = x + 1; i <= n; ++ i) {
if (e[ i ][ y ] == 1)
e[ i ] ^= e[ x ];
}
}
void gauss() {
int ind = 0;
for (int i = 1; i <= n; ++ i) {
int lin;
while (ind < m) {
lin = i;
while (lin <= n && e[ lin ][ ind ] == 0) {
++ lin;
}
if (lin <= n) {
break;
} else {
++ ind;
}
}
if (ind < m) {
swap(e[ i ], e[ lin ]);
simplifica(i, ind);
}
}
for (int i = n; i > 0; -- i) {
int pos = -1;
for (int j = 0; j < m; ++ j) {
if (e[ i ][ j ] == 1) {
pos = j; break;
}
}
if (pos != -1) {
sol[ pos ] = e[ i ][ m ];
for (int j = pos + 1; j < m; ++ j) {
sol[ pos ] ^= (e[ i ][ j ] * sol[ j ]);
}
cate += sol[ pos ];
}
}
}
void calc_lasere() {
sort(u, u + m);
double last = u[m - 1];
for (int i = 0; i < m; ++ i) {
double aux = u[ i ];
u[ i ] = (aux + last) / 2;
if (i == 0 && last - aux > pi) {
if (u[ i ] > 0) u[ i ] -= pi;
else u[ i ] += pi;
}
last = aux;
}
sort(u, u + m); sort(dr, dr + m);
int j = 0;
for (int i = 0; i < m; ++ i) {
while (j < m && dr[ j ].first < u[ i ]) {
if (dr[ j ].second < 0) viz[ -dr[ j ].second ] = 0;
else viz[ dr[ j ].second ] = 1;
++ j;
}
for (int k = 1; k <= n; ++ k) {
e[ k ][ i ] = viz[ k ];
}
}
}
int main() {
fin >> n;
for (int i = 1; i <= n; ++ i) {
fin >> v[ i ].a.x >> v[ i ].a.y >> v[ i ].b.x >> v[ i ].b.y;
baga_dr(v[ i ].a); baga_dr(v[ i ].b);
double u1 = u[m - 2], u2 = u[m - 1];
if (u1 > u2) swap(u1, u2);
if (u2 - u1 > pi) {
swap(u1, u2);
viz[ i ] = 1;
}
dr[m - 2] = make_pair(u1, i);
dr[m - 1] = make_pair(u2, -i);
}
for (int i = 1; i <= n; ++ i) {
bool aux; fin >> aux;
e[ i ][ m ] = aux;
}
calc_lasere();
gauss();
fout << cate << "\n";
fout << setprecision( 8 ) << fixed;
for (int i = 0; i < m; ++ i) {
if (sol[ i ] == 1) {
double unghi = u[ i ] * 180 / pi;
if (unghi < 0) unghi += 360;
fout << unghi << "\n";
}
}
fin.close();
fout.close();
return 0;
}