Cod sursa(job #41472)

Utilizator bogdan2412Bogdan-Cristian Tataroiu bogdan2412 Data 28 martie 2007 12:02:05
Problema Laser Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.35 kb
#include <cstdio>
#include <cmath>
#include <vector>
#include <bitset>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (int)(b); ++i)

#define Segment pair< pair<int, int>, pair<int, int> >
#define x1 first.first
#define y1 first.second
#define x2 second.first
#define y2 second.second
#define make_segment(X1, Y1, X2, Y2) make_pair( make_pair(X1, Y1), make_pair(X2, Y2) )

int N;
vector< Segment > seg;

#define MAXN 512
#define LEFT(i) ((i) << 1)
#define RIGHT(i) (LEFT(i) + 1)

double angle[ MAXN << 1 ];

bitset< MAXN << 1 > eq[MAXN];
int rez[MAXN];

vector< double > sol;

inline void getCoef( int X1, int Y1, int X2, int Y2, int &A, int &B, int &C )
{
	A = Y1 - Y2;
	B = X2 - X1;
	C = X1 * Y2 - X2 * Y1;
}

inline int sign( int A, int B, int C, int x, int y )
{
	int D = A * x + B * y + C;
	if (D > 0) return 1;
	if (D < 0) return -1;
	return 0;
}

inline void updateEqs( int A, int B, int C, int ID, int X, int Y )
{
	int A2, B2, C2;
	FOR(j, 0, N)
		if (sign(A, B, C, seg[j].x1, seg[j].y1) * sign(A, B, C, seg[j].x2, seg[j].y2) <= 0)
		{
			getCoef( seg[j].x1, seg[j].y1, seg[j].x2, seg[j].y2, A2, B2, C2 );
			if (sign(A2, B2, C2, 0, 0) * sign(A2, B2, C2, X, Y) <= 0)
				eq[j][ID] = 1;
		}
}

inline int extremePoint( int x )
{
	if (x == 0) return 0;
	if (x > 0) return 30000;
	return -30000;
}

int main()
{
	freopen("laser.in", "rt", stdin);
	freopen("laser.out", "wt", stdout);

	scanf("%d", &N);
	FOR(i, 0, N)
	{
		int X1, Y1, X2, Y2;
		scanf("%d %d %d %d", &X1, &Y1, &X2, &Y2);

		if (X1 < X2)
			seg.push_back( make_segment( X1, Y1, X2, Y2 ) );
		else
			seg.push_back( make_segment( X2, Y2, X1, Y1 ) );
	}

	FOR(i, 0, N)
		scanf("%d", rez + i);

	FOR(i, 0, N)
	{
		int A, B, C, X, Y;

		getCoef( 0, 0, seg[i].x1, seg[i].y1, A, B, C );
		angle[ LEFT(i) ] = atan2( seg[i].y1 + ((seg[i].y1 > seg[i].y2) ? 0.1 : -0.1), seg[i].x1 + 0.1 ) / M_PI * 180;
		if (angle[ LEFT(i) ] < 0)
			angle[ LEFT(i) ] += 360;
		X = extremePoint( seg[i].x1 );
		Y = extremePoint( seg[i].y1 );
		updateEqs( A, B, C, LEFT(i), X, Y );


		getCoef( 0, 0, seg[i].x2, seg[i].y2, A, B, C );
		angle[ RIGHT(i) ] = atan2( seg[i].y2 + ((seg[i].y2 > seg[i].y1) ? 0.1 : -0.1), seg[i].x2 - 0.1 ) / M_PI * 180;
		if (angle[ RIGHT(i) ] < 0)
			angle[ RIGHT(i) ] += 360;
		X = extremePoint( seg[i].x2 );
		Y = extremePoint( seg[i].y2 );
		updateEqs( A, B, C, RIGHT(i), X, Y );
	}

	int ceq = 0, lstcol = 0;
	FOR(i, 0, N << 1)
	{
		if (ceq >= N)
		{
			FOR(j, 0, N)
				eq[j][i] = 0;
			continue;
		}

		if (!eq[ ceq ][i])
		{
			FOR(j, ceq + 1, N)
				if (eq[j][i])
				{
					eq[ceq] ^= eq[j] ^= eq[ceq] ^= eq[j];
					rez[ceq] ^= rez[j] ^= rez[ceq] ^= rez[j];
					break;
				}

			if (!eq[ ceq ][i])
			{
				FOR(j, 0, i)
					eq[j][i] = 0;
				continue;
			}
		}

		FOR(j, ceq + 1, N)
			if (eq[j][i])
			{
				eq[j] ^= eq[ ceq ];
				rez[j] ^= rez[ ceq ];
			}
		ceq++; lstcol = i;
	}

	for (ceq = N - 1; ceq >= 0; ceq--)
	{
		int is1 = 0;
		FOR(i, 0, N << 1)
			if (eq[ceq][i])
				is1 = 1;

		if (!is1)
			continue;

		for (; lstcol >= 0 && !eq[ceq][lstcol]; lstcol--);

		if (lstcol < 0)
			break;

		if (rez[ceq] == 0)
		{
			FOR(i, 0, ceq)
				eq[i][lstcol] = 0;
		}
		else
		{
			sol.push_back( angle[lstcol] );
			FOR(i, 0, ceq)
				if (eq[i][lstcol])
				{
					eq[i][lstcol] = 0;
					rez[i] ^= 1;
				}
		}
		lstcol--;
	}
	
	printf("%d\n", sol.size());
	FOR(i, 0, sol.size())
		printf("%.6lf\n", sol[i]);

	return 0;
}