Cod sursa(job #1401146)

Utilizator oana28Oana Mitoiu oana28 Data 25 martie 2015 17:59:07
Problema Laser Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.62 kb
#include<fstream>
#include<iomanip>
#include<cmath>
#include<algorithm>
using namespace std;
ifstream fin("laser.in");
ofstream fout("laser.out");
const double pi=3.141592653;
struct punct
{
    int x,y;
} nul,M[1042],V[1042];
struct segment
{
    punct X,Y;
} a[528];
int n,m,nr,aux,A[528][1042],X[528];
double unghi[528];
inline int cadran(punct A)
{
    if (A.x>=0)
    {
        if (A.y>=0) return 1;
        else return 4;
    }
    else
    {
        if (A.y>=0) return 2;
        else return 3;
    }
}
inline int det(punct A, punct B, punct C)
{
    long long r=1LL*(B.x-A.x)*(C.y-A.y)-1LL*(C.x-A.x)*(B.y-A.y);
    if (!r) return 0;
    if (r<0) return -1;
    return 1;
}
inline bool inters(segment A, punct M)
{
    int r1=det(nul,A.X,M)*det(nul,A.Y,M);
    int r2=det(A.X,A.Y,M)*det(A.X,A.Y,nul);
    return r1<=0 && r2<=0;
}
bool cmp(punct A, punct B)
{
    int cA=cadran(A),cB=cadran(B);
    if (cA!=cB) return cA<cB;
    return det(A,B,nul)>0;
}
int main()
{
    int i,j,k,t;
    fin>>n;
    for (i=1;i<=n;++i)
    {
        fin>>a[i].X.x>>a[i].X.y>>a[i].Y.x>>a[i].Y.y;
        V[++m]=a[i].X, V[++m]=a[i].Y;
    }
    sort(V+1,V+m+1,cmp);
    V[m+1]=V[1];
    for (i=1;i<=m;++i)
        M[i].x=(V[i].x+V[i+1].x)*10000, M[i].y=(V[i].y+V[i+1].y)*10000;
    for (i=1;i<=n;++i)
        fin>>A[i][m+1];
    for (i=1;i<=n;++i)
        for (j=1;j<=m;++j)
            if (inters(a[i],M[j]))
                A[i][j]=1;
    i=1, j=1;
    while (i<=n)
    {
        for (t=i;t<=n+1;++t)
            if (A[t][j])
                break;
        if (t>n+1)
        {
            ++j;
            continue;
        }
        if (t==n+1)
            break;
        if (t>i)
        {
            for (t=i+1;t<=n;++t)
                if (A[t][j])
                    break;
            for (k=j;t<=n && k<=m+1;++k)
                aux=A[t][k], A[t][k]=A[i][k], A[i][k]=aux;
        }
        for (k=i+1;k<=n;++k)
            if (A[k][j])
                for (t=j;t<=m+1;++t)
                    A[k][t]+=A[i][t], A[k][t]&=1;
        ++i, ++j;
    }
    for (i=n;i>0;--i)
    {
        for (j=1;j<=m;++j)
            if (A[i][j])
                break;
        if (j>m) continue;
        X[j]=A[i][m+1];
        for (k=j+1;k<=m;++k)
            X[j]+=X[k]*A[i][k], X[j]&=1;
    }
    for (i=1;i<=m;++i)
        if (X[i])
        {
            ++nr;
            unghi[nr]=atan2(M[i].y,M[i].x)/pi*180;
            if (unghi[nr]<0) unghi[nr]+=360;
        }
    fout<<nr<<"\n";
    for (i=1;i<=nr;++i)
        fout<<setprecision(6)<<fixed<<unghi[i]<<"\n";
    return 0;
}