Cod sursa(job #1694611)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 25 aprilie 2016 17:42:21
Problema Laser Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.53 kb
#include <stdio.h>
#include <bitset>
#include <algorithm>
#include <math.h>
#define NMAX 521
#define LMAX 1055
#define pdd pair <double,double>
#define f first
#define s second
using namespace std;
int n,m,stare[NMAX],rez;
pdd A[NMAX];
double B[LMAX], C[LMAX], endPts[LMAX];
bitset <LMAX> D[NMAX],aux;
bool sol[LMAX];
 
double angle(double x,double y)
{
    double alfa=atan2(y,x)*180/M_PI;
    return alfa<0 ? alfa+360 : alfa;
}
void read()
{
    scanf("%d",&n);
    int i;
    double x,y,aux2;
    for (i=1; i<=n; i++)
    {
        scanf("%lf%lf",&x,&y);
        A[i].f=angle(x,y);
        scanf("%lf%lf",&x,&y);
        A[i].s=angle(x,y);
        if (A[i].f>A[i].s)
            aux2=A[i].f,A[i].f=A[i].s,A[i].s=aux2;
        endPts[++m]=A[i].f; endPts[++m]=A[i].s;
    }
    endPts[++m] = 0; endPts[++m] = 360;
    sort(endPts + 1, endPts + m + 1);
    int r = 0;
    for (int i = 1; i < m; i++) {
        B[++r] = (endPts[i] + endPts[i + 1]) / 2;
    }
    m = r;

    for (i=1; i<=n; i++)
        scanf("%d",&stare[i]);
}
inline double modul(double x)
{
    return x<0 ? -x : x;
}
void prepare()
{
    int i,j;
    double alfa;
     
    for (i=1; i<=m; i++)
        for (j=1; j<=n; j++)
        {
            alfa=A[j].s-A[j].f;
            if (alfa<180)
            {
                if (A[j].f<=B[i] && B[i]<=A[j].s)
                    D[j][i]=1;
            }
            else
            {
                if ((B[i]>=A[j].s && B[i]<=360) || (B[i]>=0 && B[i]<=A[j].f))
                    D[j][i]=1;
            }
        }
    for (i=1; i<=n; i++)
        D[i][m+1]=stare[i];
}
void swap(int lx,int ly)
{
    aux=D[lx]; D[lx]=D[ly]; D[ly]=aux;
}
void gauss()
{
    int i=1,j=1,k;
    while (i<=n && j<=m)
    {
        for (k=i; k<=n; k++)
            if (D[k][j])
                break ;
        if (k==n+1)
        {
            j++;
            continue ;
        }
        if (i!=k)
            swap(i,k);
        for (k=i+1; k<=n; k++)
            if (D[k][j])
                D[k]^=D[i];
        i++; j++;
    }
    for (i=n; i>=1; i--)
        for (j=1; j<=m+1; j++)
            if (D[i][j])
            {
                sol[j]=D[i][j+1];
                for (k=m; k>j; k--)
                    sol[j]^=sol[k] & D[i][k];
                break ;
            }
    for (i=1; i<=m; i++)
        if (sol[i])
            rez++;
    printf("%d\n",rez);
    for (i=1; i<=m; i++)
        if (sol[i])
            printf("%.6lf\n",B[i]);
}
int main()
{
    freopen("laser.in","r",stdin);
    freopen("laser.out","w",stdout);
    read();
    prepare();
    gauss();
    return 0;
}