Cod sursa(job #41100)

Utilizator bogdan2412Bogdan-Cristian Tataroiu bogdan2412 Data 27 martie 2007 22:41:53
Problema Laser Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.73 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;
		}
}

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);

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

	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].x1 ) / M_PI * 180;
		if (angle[ LEFT(i) ] < 0)
			angle[ LEFT(i) ] += 360;
		X = 30000;
		if ( seg[i].x1 < 0 )
			X = -30000;
		Y = 30000;
		if ( seg[i].y1 < 0 )
			Y = -30000;
		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].x2 ) / M_PI * 180;
		if (angle[ RIGHT(i) ] < 0)
			angle[ RIGHT(i) ] += 360;
		X = 30000;
		if ( seg[i].x2 < 0 )
			X = -30000;
		Y = 30000;
		if ( seg[i].y2 < 0 )
			Y = -30000;
		updateEqs( A, B, C, RIGHT(i), X, Y );
	}

	int ceq = 0;
	FOR(i, 0, N << 1)
	{
		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])
				continue;
		}

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

	ceq = 0;
	FOR(i, 0, N << 1)
	{
		if (ceq >= N)
			break;

		if (!eq[ ceq ][i])
			continue;

		if (rez[ ceq ])
			sol.push_back( angle[i] );
		ceq++;
	}

	printf("%d\n", sol.size());
	FOR(i, 0, sol.size())
		printf("%lf\n", sol[i]);

	return 0;
}