Cod sursa(job #1756734)

Utilizator Cristian1997Vintur Cristian Cristian1997 Data 13 septembrie 2016 15:54:13
Problema Laser Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.78 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&);
bool inInt(pii, pii, pii, pii);
int area(pii, pii, pii);
int cp(pii, pii, pii);
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[j].x, segs[j].y, segs[i])) v[i][j] = true;
			if (intersect(segs[j].z, segs[j].t, segs[i])) v[i][j + 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; }
		if (j >= 2 * n) continue;

		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)
{
	if (inInt({0, 0}, {s.x, s.y}, {s.z, s.t}, {x, y})) return true;

	int a = cp({s.x, s.y}, {s.z, s.t}, {0, 0});
	int b = cp({s.x, s.y}, {s.z, s.t}, {x, y});

	if (a < 0 && b > 0) return true;
	if (a > 0 && b < 0) return true;
	return false;
}

bool inInt(pii a, pii b, pii c, pii p)
{
	return area(a, b, p) + area(b, c, p) + area(c, a, p) == area(a, b, c);
}

int area(pii a, pii b, pii c)
{
	int s = cp(a, b, c);

	return (s > 0 ? s : -s);
}

int cp(pii a, pii b, pii c)
{
	return (b.first - a.first) * (c.second - a.second) - (c.first - a.first) * (b.second - a.second);
}

double degree(int x, int y)
{
	double angle = atan2(y, x) * 180.0 / acos(-1);
	if (angle < 0) angle += 360.0;

	return angle;
}