Pagini recente » Cod sursa (job #98321) | Cod sursa (job #693651) | Cod sursa (job #1586026) | Cod sursa (job #1565101) | Cod sursa (job #587721)
Cod sursa(job #587721)
#include <cstdio>
#include <cmath>
using namespace std;
const int N = 520;
int n, s[N], xs[N], ys[N], xf[N], yf[N];
void read() {
scanf("%d", &n);
for (int i = 1; i <= n; ++ i)
scanf("%d%d%d%d", &xs[i], &ys[i], &xf[i], &yf[i]);
for (int i = 1; i <= n; ++ i)
scanf("%d", &s[i]);
}
double angle(int x, int y) {
double a = asin((double)y / sqrt((double)x * x + y * y)) / M_PI * 180;
if (x >= 0 && y >= 0)
return a;
if (x <= 0 && y >= 0)
return (double)180 - a;
if (x <= 0 && y <= 0)
return (double)180 - a;
return (double)360 + a;
}
double u1[N], u2[N], v[2 * N];
int lv;
#include <algorithm>
void angles() {
for (int i = 1; i <= n; ++ i) {
u1[i] = v[++ lv] = angle(xs[i], ys[i]);
u2[i] = v[++ lv] = angle(xf[i], yf[i]);
if (u1[i] > u2[i])
swap(u1[i], u2[i]);
}
}
#include <bitset>
bitset <2 * N> g[N];
bool inters(double x1, double x2, double x3) {
if (x2 - x1 > 360 - x2 + x1) {
if ((x3 >= x2 && x3 <= 360) || (x3 >= 0 && x3 <= x1))
return 1;
return 0;
}
if (x3 >= x1 && x3 <= x2)
return 1;
return 0;
}
int m;
void init_gauss() {
m = 2 * n;
for (int i = 1; i <= n; ++ i) {
for (int j = 1; j <= m; ++ j)
if (inters(u1[i], u2[i], v[j]))
g[i][j] = 1;
g[i][0] = s[i];
}
}
bool used[2 * N];
int line[2 * N];
void gauss() {
bitset <2 * N> aux;
for (int c = 1, r = 1; c <= m; ++ c) {
int raux = 0;
for (raux = r; raux <= n; ++ raux)
if (g[raux][c])
break;
if (raux == n + 1)
continue;
if (raux != r) {
aux = g[r];
g[r] = g[raux];
g[raux] = aux;
}
for (int i = r + 1; i <= n; ++ i)
if (g[i][c])
g[i] ^= g[r];
line[c] = r ++;
}
int nru = 0;
for (int c = m; c >= 0; -- c) {
if (! line[c])
continue;
used[c] = g[line[c]][0];
for (int i = c + 1; i <= m; ++ i)
used[c] ^= g[line[c]][i] & used[i];
if (used[c])
++ nru;
}
printf("%d\n", nru);
for (int i = 1; i <= m; ++ i)
if (used[i])
printf("%lf\n", v[i]);
}
int main() {
freopen("laser.in", "r", stdin);
freopen("laser.out", "w", stdout);
read();
angles();
init_gauss();
gauss();
return 0;
}