Cod sursa(job #1863615)

Utilizator RazvanR104Razvan-Andrei Ciocoiu RazvanR104 Data 31 ianuarie 2017 02:19:15
Problema Laser Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.62 kb
#include <bits/stdc++.h>

using namespace std;

const int64_t NMAX = 600;
const double PI = acos(-1);

int64_t N;
int64_t A[NMAX][2 * NMAX];
int64_t val[2 * NMAX];

struct Point {
	double x, y;
	Point(double x = 0, double y = 0):
		x(x), y(y) {
	}
	static double crossProduct(const Point &A, const Point &B, const Point &C) {
		return A.x * B.y + B.x * C.y + C.x * A.y - C.x * B.y - A.x * C.y - B.x * A.y;
	}
	bool operator<(const Point &rhs) const {
		return crossProduct(Point(), *this, rhs) > 0;
	}
} arrPoints[2 * NMAX], bisPoints[2 * NMAX];
pair<Point, Point> lineSegment[NMAX];

bool lineSegmentIntersect(Point A, pair<Point, Point> B) {
	return Point::crossProduct(Point(), A, B.first) * Point::crossProduct(Point(), A, B.second) < 0 && Point::crossProduct(B.first, B.second, Point()) * Point::crossProduct(B.first, B.second, A) < 0;
}

int main() {
	assert(freopen("laser.in", "r", stdin));
	assert(freopen("laser.out", "w", stdout));

	int64_t i, j, k, l;
	cin >> N;
	for (i = 1; i <= N; ++i) {
		int64_t a, b, c, d;
		cin >> a >> b >> c >> d;
		lineSegment[i] = {Point(a, b), Point(c, d)};
		arrPoints[2 * i - 1] = lineSegment[i].first;
		arrPoints[2 * i] = lineSegment[i].second;
	}
	for (i = 1; i <= N; ++i)
		cin >> A[i][2 * N + 1];

	sort(arrPoints + 1, arrPoints + 2 * N + 1);
	arrPoints[2 * N + 1] = arrPoints[1];
	for (i = 1; i <= 2 * N; ++i)
		bisPoints[i] = {((arrPoints[i].x + arrPoints[i + 1].x) / 2) * 20000, ((arrPoints[i].y + arrPoints[i + 1].y) / 2) * 20000};

	for (i = 1; i <= N; ++i)
		for (j = 1; j <= 2 * N; ++j)
			if (lineSegmentIntersect(bisPoints[j], lineSegment[i]))
				A[i][j] = 1;

	i = j = 1;
	while (i <= N && j <= 2 * N) {
		for (k = i; A[k][j] == 0 && k <= N; ++k);
		--k;
		if (!A[k][j]) {
			++j;
			continue;
		}
		if (k != i)
			for (l = 1; l <= 2 * N + 1; ++l)
				swap(A[i][l], A[k][l]);
		for (k = i + 1; k <= N; ++k)
			if (A[k][j])
				for (l = j; l <= 2 * N + 1; ++l) {
					A[k][l] -= A[i][l];
					if (A[k][l] < 0)
						A[k][l] += 2;
				}
		++i, ++j;
	}

	for (i = N; i >= 1; --i) {
		int64_t value = A[i][2 * N + 1];
		int64_t pos = -1;
		for (j = 2 * N; j >= 1; --j) {
			value -= A[i][j] * val[j];
			if (A[i][j])
				pos = j;
		}
		if (pos != -1)
			val[pos] = (value % 2 + 2) % 2;
	}

	int64_t answer = 0;
	for (i = 1; i <= 2 * N; ++i)
		answer += val[i] > 0;
	cout << answer << '\n';
	cout << fixed << setprecision(6);
	for (i = 1; i <= 2 * N; ++i) {
		if (val[i] == 0)
			continue;
		double res = atan2(bisPoints[i].y, bisPoints[i].x) * 180 / PI;
		if (res < 0)
			res += 360;
		cout << res << '\n';
	}

	return 0;
}