Pagini recente » Clasament dupa rating | Cod sursa (job #1184328) | Monitorul de evaluare | Istoria paginii utilizator/darksp1der | Cod sursa (job #1762672)
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <bitset>
#include <cassert>
#define fi first
#define se second
#define mPair make_pair
using namespace std;
const int kMaxN = 2 * 550;
const double kPi = acos(-1.0);
int n;
pair <bool, pair <pair <int, int>, pair <int, int>>> Segs[kMaxN];
pair <int, int> segEnds[2 * kMaxN];
bitset<kMaxN> Gauss[2 * kMaxN];
bool eqSol[2 * kMaxN];
bool trigSort(const pair <int, int> &a, const pair <int, int> &b) {
return atan2(a.se, a.fi) < atan2(b.se, b.fi);
}
void rowEchelon() {
int i = 1, j = 1;
while (i <= n and j <= 2 * n) {
int k = i;
while (k <= n and Gauss[k][j] == false) {
k += 1;
}
if (k <= n) {
swap(Gauss[i], Gauss[k]);
k += 1;
while (k <= n) {
if (Gauss[k][j] == true) {
Gauss[k] ^= Gauss[i];
}
k += 1;
}
i += 1;
}
j += 1;
}
}
int main() {
freopen("laser.in", "r", stdin);
freopen("laser.out", "w", stdout);
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d %d", &segEnds[2 * i - 1].fi, &segEnds[2 * i - 1].se);
scanf("%d %d", &segEnds[2 * i].fi, &segEnds[2 * i].se);
Segs[i].se.fi = segEnds[2 * i - 1];
Segs[i].se.se = segEnds[2 * i];
}
for (int i = 1; i <= n; i++) {
scanf("%d", &Segs[i].fi);
Gauss[i][2 * n + 1] = Segs[i].fi;
}
sort(segEnds + 1, segEnds + 2 * n + 1, trigSort);
for (int i = 1; i <= 2 * n; i++) {
double xm = (segEnds[i].fi + segEnds[i == 2 * n ? 1 : i + 1].fi) / 2.0;
double ym = (segEnds[i].se + segEnds[i == 2 * n ? 1 : i + 1].se) / 2.0;
for (int j = 1; j <= n; j++) {
double fiSlope = atan2(Segs[j].se.fi.se, Segs[j].se.fi.fi);
double seSlope = atan2(Segs[j].se.se.se, Segs[j].se.se.fi);
double mSlope = atan2(ym, xm);
if (fabs(fiSlope - seSlope) > kPi) mSlope += kPi;
if (min(fiSlope, seSlope) <= mSlope && mSlope <= max(fiSlope, seSlope)) {
Gauss[j][i] = true;
}
}
}
rowEchelon();
for (int i = n; i >= 1; i--) {
int j = i;
while (j <= 2 * n and Gauss[i][j] == false) {
j += 1;
}
if (j < 2 * n + 1) {
eqSol[j] = Gauss[i][2 * n + 1];
for (int k = j + 1; k <= 2 * n; k += 1) {
if (Gauss[i][k] == true) {
eqSol[j] ^= eqSol[k];
}
}
}
}
vector <double> Shoot;
for (int i = 1; i <= 2 * n; i++) {
if (eqSol[i] == true) {
double xm = (segEnds[i].fi + segEnds[i == 2 * n ? 1 : i + 1].fi) / 2.0;
double ym = (segEnds[i].se + segEnds[i == 2 * n ? 1 : i + 1].se) / 2.0;
double mSlope = atan2(ym, xm);
while (mSlope < 0) mSlope += 2 * kPi;
Shoot.push_back(mSlope * 180 / kPi);
}
}
printf("%u\n", Shoot.size());
for (const double x: Shoot) {
printf("%.15f\n", x);
}
return 0;
}