Cod sursa(job #1252867)

Utilizator geniucosOncescu Costin geniucos Data 31 octombrie 2014 14:34:20
Problema Laser Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.38 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;
    }

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

double Det_Unghi(double x, double y)
{
    double result = (double)atan2 (y,x) * 180 / M_PI;
    if (result < 0) result = 360 + result;
    return result;
}

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

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

/*for (int i=1; i<=4; 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;
    S = Det_Unghi ( a1 [ i ] , b1 [ i ] ) ;
    D = Det_Unghi ( a2 [ i ] , b2 [ i ] ) ;

    if (S < D)
        st[i] = S, dr[i] = D;
    else
        st[i] = D, dr[i] = S;

    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++)
{
    for (int j=1; j<=nr_unghiuri_utile; j++)
        if (unghiuri_utile[j] >= st[i] && unghiuri_utile[j] <= dr[i])
            A[i][j] = 1;
    A[i][nr_unghiuri_utile + 1] = tip[i];
}

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;
    for (int j=1; j<=n; j++)
        if (i != j && A[j][p])
            A[j] ^= A[i];
}

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