Pagini recente » Cod sursa (job #3039948) | Cod sursa (job #2854442) | Cod sursa (job #2150565) | Cod sursa (job #2887892) | Cod sursa (job #3257653)
//https://infoarena.ro/problema/laser
//#pragma GCC optimize ("Ofast")
//#pragma GCC optimize ("fast-math")
//#pragma GCC optimize ("unroll-loops")
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <fstream>
#include <cmath>
#include <vector>
#include <bitset>
#include <iomanip>
using namespace std;
const double PI = acos(-1);
ifstream fin ("laser.in");
ofstream fout ("laser.out");
int col[520];
vector <pair <double, double>> v;
vector <double> p, x, rez;
bitset <2100> bit[2100];
bool seIntersecteaza(pair<double,double> seg,double xx)
{
double a = seg.first;
double b = seg.second;
if (a > b)
swap(a, b);
if (b - a < PI)
return xx >= a && xx <= b;
return xx <= a || xx >= b;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, i, j;
fin >> n;
for (i = 0; i < n; ++i)
{
int x1, x2, y1, y2;
fin >> x1 >> y1 >> x2 >> y2;
double aatan2 = atan2(y1, x1);
double batan2 = atan2(y2, x2);
double a = (aatan2 + (aatan2 < 0.0) * 2 * PI);
double b = (batan2 + (batan2 < 0.0) * 2 * PI);
//cout << a << " " << b << "\n";
v.emplace_back(a, b);
p.push_back(a);
p.push_back(b);
}
sort(p.begin(), p.end());
p.push_back(p[0] + 2 * PI);
x.resize(4 * n);
for (i = 0; i < 2 * n; ++i)
{
x[2 * i] = p[i];
x[2 * i + 1] = ((p[i] + p[i + 1]) / 2);
}
if (x.back() >= 2 * PI)
{
x.insert(x.begin(), x.back() - 2 * PI);
x.pop_back();
}
for (i = 0; i < n; ++i)
{
bool b;
fin >> b;
if (b == 1)
{
bit[i][n * 4] = 1;
}
}
for (i = 0; i < n; ++i)
{
for (j = 0; j < 4 * n; ++j)
{
bit[i][j] = seIntersecteaza(v[i], x[j]);
}
}
int r, c;
r = 0;
c = 0;
while ((r < n) && (c < 4 * n))
{
if (!bit[r][c])
{
i = r + 1;
while ((i < n) && (!bit[i][c]))
{
++i;
}
if (i == n)
{
++c;
continue;
}
swap(bit[r], bit[i]);
}
if (bit[r][c])
{
for (i = 0; i < n; ++i)
{
if ((i != r) && (bit[i][c]))
{
bit[i] ^= bit[r];
}
}
}
col[r] = c;
++c;
++r;
}
for (i = 0; i < n; ++i)
{
if (bit[i][4 * n])
rez.push_back(x[col[i]] / PI * 180);
}
fout << rez.size() << "\n";
fout << setprecision(6) << fixed;
for (double i : rez)
{
fout << i << "\n";
}
return 0;
}