Cod sursa(job #1252928)

Utilizator geniucosOncescu Costin geniucos Data 31 octombrie 2014 16:21:09
Problema Laser Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.74 kb
#include<cstdio>
#include<bitset>
#include<cmath>

using namespace std;

int j, n, n_sol, nr_unghiuri_utile, a1[530], b1[530], a2[530], b2[530], pos[1030], ap[1030], tip[520];
double eps, unghiuri_utile[1030], sol[1030], st[530], dr[530];

bitset < 1030 > A[520];

double Det_Unghi(double x, double y)
{
    if (x >= -eps && x <= eps)
    {
        if ( y > -eps ) return 90.0;
        return 270.0;
    }

    if (y >= -eps && y <= eps)
    {
        if ( x > -eps ) return 0.0;
        return 180.0;
    }
    double ip = (double) sqrt ( (double) x * x + y * y );

    if (x > -eps && y > -eps)
        return (double) acos ( (double) x /  ip ) * 180 / M_PI;

    if (y > -eps)
        return (double) 180.0 - acos ( (double) (-x) /  ip ) * 180 / M_PI;

    if (x > -eps)
        return (double) 360.0 - acos ( (double) x /  ip ) * 180 / M_PI;

    return (double) 180.0 + acos ( (double) (-x) /  ip ) * 180 / M_PI;
}

void afis ()
{
    for (int i=1; i<=n; i++, printf ( "\n" ) )
        for (int j=1; j<=nr_unghiuri_utile + 1; j++)
        {
            if (A[i][j] == 1) printf ("1");
            else printf ("0");
        }
    printf ("\n\n\n");
}

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

scanf ("%d", &n);
eps = 0.000001;

/*for (int i=1; i<=1; i++)
{
    int a, b;
    scanf ("%d %d", &a, &b);
    printf ("%.5lf\n", Det_Unghi (a, b) );
}
return 0;*/

for (int i=1; i<=n; i++)
{
    scanf ("%d %d %d %d", &a1[i], &b1[i], &a2[i], &b2[i]);

    double S, D, Mij;
    S = Det_Unghi ( a1 [ i ] , b1 [ i ] ) ;
    D = Det_Unghi ( a2 [ i ] , b2 [ i ] ) ;
    Mij = Det_Unghi ( (double) ( a1[i] + a2[i] ) / 2.0, (double) ( b1[i] + b2[i] ) / 2.0 );
    if (S > D)
    {
        double aux = S;
        S = D;
        D = aux;
    }
    if (Mij >= S + eps && Mij <= D - eps)
        st[i] = S, dr[i] = D;
    else
        st[i] = D, dr[i] = S;
    if (st[i] <= dr[i])
    {
        unghiuri_utile [++ nr_unghiuri_utile] = st[i] + eps;
        unghiuri_utile [++ nr_unghiuri_utile] = dr[i] - eps;
    }
    else
    {
        unghiuri_utile [++ nr_unghiuri_utile] = st[i] - eps;
        unghiuri_utile [++ nr_unghiuri_utile] = dr[i] + eps;
    }
}

for (int i=1; i<=n; i++)
{
    scanf ("%d", &tip[i]);
    //printf ("%.3lf %.3lf %d\n", st[i], dr[i], tip[i]);
}

//printf ("\n\n\n");

for (int i=1; i <= n; i++)
{
    if (st[i] <= dr[i])
    {
        for (int j=1; j<=nr_unghiuri_utile; j++)
            if (unghiuri_utile[j] >= st[i] && unghiuri_utile[j] <= dr[i])
                A[i][j] = 1;
    }
    else
    {
        for (int j=1; j<=nr_unghiuri_utile; j++)
            if (unghiuri_utile[j] < dr[i] || unghiuri_utile[j] > st[i]) ;
            else
            A[i][j] = 1;
    }
    A[i][nr_unghiuri_utile + 1] = tip[i];
}

//for (int i=1; i<=nr_unghiuri_utile; i++)
  //  printf ("%.5lf\n", unghiuri_utile[i]);

//afis ();
//return 0;
for (int i=1; i<=n; i++)
{
    int p = 0;
    for (j=1; j<=nr_unghiuri_utile + 1; j++)
        if (A[i][j])
        {
            p = j;
            break;
        }
    pos[i] = p;
    if (p == 0) continue;
    /*if (p == nr_unghiuri_utile + 1)
    {
        printf ("finish");
        return 0;
        while (1)
        {
            int ff;
            ff++;

        }
    }*/
    for (int j=1; j<=n; j++)
        if (i != j && A[j][p])
            A[j] ^= A[i];
    //afis ();
}

for (int i=1; i<=n; i++)
    if (A[i][nr_unghiuri_utile + 1])
        ap[pos[i]] = 1;

for (int i=1; i<=nr_unghiuri_utile; i++)
    if (ap[i])
        sol[++n_sol] = unghiuri_utile[i];

printf ("%d\n", n_sol);
for (int i=1; i<=n_sol; i++)
    printf ("%.6lf\n", sol[i]);

return 0;
}