Cod sursa(job #793987)

Utilizator danalex97Dan H Alexandru danalex97 Data 4 octombrie 2012 21:46:10
Problema Laser Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 7.3 kb
//#include <algorithm>
//#include <fstream>
//#include <bitset>
//#include <cmath>
//using namespace std;
//
//ifstream F("laser.in");
//ofstream G("laser.out");
//
//const int Nmax = 2010;
//const int oo = 1<<20;
//const double EPS = 0.0000001;
//
//#define mp make_pair
//#define m first.first
//#define x second.first
//#define y second.second
//
//typedef pair< double,pair<int,int> > Grupe;
//typedef pair< double,double > Pair;
//
//int N,M;
//
//Grupe Dr[Nmax];
//
//#define X first
//#define Y second
//Pair Bis[Nmax];
//pair<Pair,Pair> St[Nmax];
//
//int A[Nmax][Nmax];
//int V[Nmax];
//
//void Gauss();
//void Drepte();
//void Make();
//
//Pair Intersect(int i1,int i2)
//{
//    double xA,xB,yA,yB;
//    xA = yA = 0;
//    xB = Bis[i1].X;
//    yB = Bis[i1].Y;
//    if ( xB < xA || ( xB == xA && yB < yA ) )
//        swap( xA , xB ) ,
//        swap( yA , yB ) ;
//
//    double a = yA - yB ;
//    double b = xB - xA ;
//    double c = -xB * yA + yB * xA ;
//
//    xA = St[i2].X.X;
//    yA = St[i2].X.Y;
//    xB = St[i2].Y.X;
//    yB = St[i2].Y.Y;
//    if ( xB < xA || ( xB == xA && yB < yA ) )
//        swap( xA , xB ) ,
//        swap( yA , yB ) ;
//
//    double aa = yA - yB ;
//    double bb = xB - xA ;
//    double cc = -xB * yA + yB * xA ;
//
//    double D=a*bb-aa*b;
//
//    if (fabs(D)<EPS)
//        return mp(-2*oo,-2*oo);
//    return mp((bb*c-b*cc)/D,(a*cc-aa*c)/D);
//}
//
//int Int(int i1,int i2)
//{
//    Pair Pdd = Intersect( i1 , i2 );
//    int xA,xB,yA,yB;
//    xA = St[i2].X.X;
//    yA = St[i2].X.Y;
//    xB = St[i2].Y.X;
//    yB = St[i2].Y.Y;
//    if ( xB < xA || ( xB == xA && yB < yA ) )
//        swap( xA , xB ) ,
//        swap( yA , yB ) ;
//    if ( Pdd.X > xA && Pdd.X < xB )
//        if ( Pdd.Y > yA && Pdd.Y < yB )
//            return 1;
//    return 0;
//}
//
//int main()
//{
//    Drepte();
//    Make();
//    Gauss();
//}
//
//void Make()
//{
//    M = N >> 1;
//    for (int i=1;i<=N;++i)
//        for (int j=1;j<=M;++j)
//            A[i][j] = Int(i,j);
//}
//
//void Drepte()
//{
//    F>>N;
//    for (int i=1;i<=N;++i)
//    {
//        double xA,yA,xB,yB;
//        F>>xA>>yA>>xB>>yB;
//        St[i] = mp( mp(xA,yA) , mp(xB,yB) );
//
//        Dr[i]= mp( yA/xA , mp( xA , yA ) );
//        Dr[N+i]= mp( yB/xB , mp( xB , yB ) );
//    }
//    sort( Dr+1 , Dr+2*N+1 );
//
//    N <<= 1;
//
//    Dr[N+1]=Dr[1];
//    for (int i=1;i<=N;++i)
//    {
//        Pair Pdd;
//        Pdd.first = ( double( Dr[i].x + Dr[i+1].x ) ) / 2.0 ;
//        Pdd.second = ( double(Dr[i].y + Dr[i+1].y ) ) / 2.0 ;
//        Bis[i]=Pdd;
//    }
//}
//
//void Gauss()
//{
//    for (int i=1,j=1,k;i<=N && j<=M;++i,++j)
//    {
//        for ( k=i;k<=N;++k )
//            if ( A[k][j]<-EPS || A[k][j]>EPS )
//                break;
//        if ( k==N+1 )
//        {
//            --i;
//            continue;
//        }
//
//        if ( i != k )
//            for (int l=1;l<=M+1;++l)
//                swap(A[i][l],A[k][l]);
//
//        for (int l=j+1;l<=M+1;++l)
//            A[i][l] /= A[i][j];
//        A[i][j]=1;
//
//        for(int u=i+1;u<=N;++u)
//        {
//            for(int l=j+1;l<=M+1;++l)
//                A[u][l]-=A[u][j]*A[i][l];
//            A[u][j] = 0;
//        }
//    }
//
//    for (int i=N;i;--i)
//        for (int j=1;j<=M+1;++j)
//            if ( A[i][j]<-EPS || A[i][j]>EPS )
//            {
//                V[j] = A[i][M+1];
//                for(int k=j+1;k<=M;++k)
//                    V[j] -= V[k]*A[i][k];
//                break;
//            }
//}

#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 void getExtremePoint( int x, int y, int &rx, int &ry )
{
	if (x == 0)
	{
		rx = 0;
		ry = (y > 0) ? 30000 : -30000;
		return;
	}
	if (y == 0)
	{
		rx = (x > 0) ? 30000 : -30000;
		ry = 0;
		return;
	}

	rx = (x > 0) ? 30000 : -30000;
	ry = rx * y / x;

	if (ry > 30000 || ry < -30000)
	{
		ry = (y > 0) ? 30000 : -30000;
		rx = ry * x / y;
	}
}

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