Cod sursa(job #1756256)

Utilizator Cristian1997Vintur Cristian Cristian1997 Data 12 septembrie 2016 14:32:33
Problema Laser Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.32 kb
#include <fstream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
#include <bitset>
#include <cmath>
using namespace std;
using ll = long long;
using uint = unsigned int;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define NMAX 1030

struct seg
{
	int x, y, z, t;
	seg(int _x, int _y, int _z, int _t) : x(_x), y(_y), z(_z), t(_t) {}
};

vector<seg> segs;
bitset<NMAX> v[NMAX], x;

bool intersect(int, int, const seg&);
double degree(int, int);

int main()
{
	int i, j, k, n;
	ifstream fin("laser.in");
	ofstream fout("laser.out");

	fin >> n;
	for (i = 0; i < n; ++i)
	{
		int a, b, c, d;
		fin >> a >> b >> c >> d;
		segs.emplace_back(a, b, c, d);
	}

	for (i = 0; i < n; ++i)
	{
		for (j = 0; j < n; ++j)
		{
			if (intersect(segs[i].x, segs[i].y, segs[j])) v[j][i] = true;
			if (intersect(segs[i].z, segs[i].t, segs[j])) v[j][i + n] = true;
		}
	}

	for (i = 0; i < n; ++i) { int a; fin >> a; v[i][2 * n] = a; }

	for (i = j = 0; i < n && j < 2 * n; )
	{
		for (k = i; k < n; ++k) if (v[k][j]) break;

		if (k >= n) { ++j; continue; }
		if (k != i) swap(v[i], v[k]);

		for (k = i + 1; k < n; ++k) if (v[k][j]) v[k] ^= v[i];

		++i; ++j;
	}

	/*for (i = 0; i < n; ++i)
	{
		for (j = 0; j <= 2 * n; ++j)
			if (v[i][j]) fout << 1;
			else fout << 0;
			fout << '\n';
	}*/

	for (i = n - 1; i >= 0; --i)
	{
		for (j = 0; j < 2 * n; ++j) { if (v[i][j]) break; }

		x[j] = v[i][2 * n];
		for (k = j + 1; k < 2 * n; ++k) x[j] = x[j] ^ (v[i][k] & x[k]);
	}

	fout << x.count() << '\n';

	for (i = 0; i < 2 * n; ++i)
	{
		if (x[i])
		{
			double angle;

			if (i < n) angle = degree(segs[i].x, segs[i].y);
			else angle = degree(segs[i - n].z, segs[i - n].t);

			fout << fixed << setprecision(6) << angle << '\n';
		}
	}

	fin.close();
	fout.close();

	return 0;
}

bool intersect(int x, int y, const seg &s)
{
	double ang1 = degree(s.x, s.y);
	double ang2 = degree(s.z, s.t);
	double ang = degree(x, y);

	if (ang1 > ang2) swap(ang1, ang2);

	if (ang2 - ang1 < 180.0) return (ang1 <= ang && ang <= ang2);
	return (ang <= ang1 || ang >= ang2);
}


double degree(int x, int y)
{
	double angle = atan2(y, x) * 57.295779513;
	if (angle < 0) angle += 360.0;

	return angle;
}