Cod sursa(job #3257653)

Utilizator Cezar2009Cezar Mihai Titihazan Cezar2009 Data 18 noiembrie 2024 19:21:17
Problema Laser Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.33 kb
//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;
}