Cod sursa(job #1385377)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 11 martie 2015 21:56:55
Problema Laser Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.76 kb
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>

#define DIM 550
#define pi 3.141592653
#define x first
#define y second
#define infile "laser.in"
#define outfile "laser.out"

using namespace std;

ifstream fin(infile);
ofstream fout(outfile);

struct segment {

	double x1, y1;
	double x2, y2;

} segments[DIM];

int a[DIM][2 * DIM];

int ok[2 * DIM], aprins[DIM];

pair<double, double> vec[2 * DIM], p0 = make_pair(0, 0);

double det(pair<double, double> a, pair<double, double> b, pair<double, double> c) {

	return (a.x - c.x)*(b.y - c.y) - (a.y - c.y)*(b.x - c.x);

}

bool cmp(const pair<double, double> &a, const pair<double, double> &b) {

	return (det(a, b, p0) < 0);

}

bool segIntersection(pair<double, double> a, pair<double, double> b, pair<double, double> c, pair<double, double> d) {

	if (1LL * det(a, b, c)*det(a, b, d) < 0 && 1LL * det(c, d, a)*det(c, d, b) < 0)
		return true;

	return false;

}

int main() {

	int n, m = 0;

	fin >> n;

	for (int i = 1; i <= n; ++i) {

		fin >> segments[i].x1 >> segments[i].y1 >> segments[i].x2 >> segments[i].y2;
		vec[++m] = make_pair(segments[i].x1, segments[i].y1);
		vec[++m] = make_pair(segments[i].x2, segments[i].y2);

	}

	for (int i = 1; i <= n; ++i)
		fin >> aprins[i];

	sort(vec + 1, vec + m + 1, cmp);

	vec[m + 1] = vec[1];

	for (int i = 1; i <= m; ++i) {
	
		vec[i].x = ((vec[i].x + vec[i + 1].x) / 2) * 10005;
		vec[i].y = ((vec[i].y + vec[i + 1].y) / 2) * 10005;
	
	}

	for (int i = 1; i <= n; ++i) {

		for (int j = 1; j <= m; ++j) {

			if (segIntersection(make_pair(segments[i].x1, segments[i].y1), make_pair(segments[i].x2, segments[i].y2), vec[j], p0))
				a[i][j] = 1;

		}

		a[i][m + 1] = (aprins[i] ? 1 : 0);

	}

	int i = 1, j = 1;

	while (i <= n && j <= m) {

		int k;

		for (k = i; k <= n; ++k)
			if (a[k][j])
				break;

		if (k == n + 1) {

			++j;
			continue;

		}

		for (int l = 1; l <= m + 1; ++l)
			swap(a[i][l], a[k][l]);

		for (k = i + 1; k <= n; ++k) {

			if (a[k][j] == 0)
				continue;

			for (int l = j; l <= m + 1; ++l)
				a[k][l] = (a[k][l] + a[i][l]) % 2;

		}

		++i, ++j;

	}

	for (int i = n; i; --i) {

		for (int j = 1; j <= m; ++j) {

			if (a[i][j]) {

				ok[j] = a[i][m + 1];

				for (int l = j + 1; l <= m; ++l)
					ok[j] = (ok[j] + ok[l] * a[i][l]) % 2;

			}

		}

	}

	int sol = 0;

	for (int i = 1; i <= m; ++i)
		if (ok[i])
			++sol;

	fout << sol << '\n';

	for (int i = 1; i <= m; ++i) {

		if (!ok[i])
			continue;

		double res = atan2(vec[i].y, vec[i].x) * 180 / pi;

		if (res < 0)
			res += 360;

		fout << setprecision(6) << fixed << res << '\n';

	}

	return 0;
}

//Trust me, I'm the Doctor!