Cod sursa(job #1955683)

Utilizator Bodo171Bogdan Pop Bodo171 Data 6 aprilie 2017 10:04:18
Problema Laser Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.02 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <bitset>
#include <cmath>
#include <iomanip>
using namespace std;
const int nmax=520;
bitset<2*nmax> a[nmax],current;
struct point
{
    int x,y,tip;
}v[2*nmax],orig;
long double unghi[2*nmax];
long double xst,xdr,yst,ydr,angle,conv=180;
int i,n,j,ind,k,nr,X1,Y1,X2,Y2;
int p[nmax];
bool ok;
int det(point A,point B,point C)
{
    return A.x*B.y+B.x*C.y+C.x*A.y+A.y*B.x+B.y*C.x+C.y*A.x;
}
long double get_angle(long double x,long double y)
{
    angle=atan2(y,x);
    if(angle<0) angle+=2*M_PI;
    return (angle/M_PI*conv);
}
bool trigo(point unu,point doi)
{
    //return (det(orig,unu,doi)>0);
    return get_angle(unu.x,unu.y)<get_angle(doi.x,doi.y);
}
void baleiere()
{
    for(i=1;i<=2*n;i++)
    {
        if(current[v[i].tip]) current[v[i].tip]=0;
        else current[v[i].tip]=1;
        k++;
        for(j=1;j<=n;j++)
            a[j][k]=current[j];
        xst=v[i].x;xdr=v[i+1].x;
        yst=v[i].y;ydr=v[i+1].y;
        unghi[k]=get_angle((xst+xdr)/2,(yst+ydr)/2);
    }
}
void gauss()
{
    //n linii,k+1,coloane
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=k&&p[i]==0;j++)
            if(a[i][j])
              p[i]=j;
        if(p[i]==0) continue;
        for(ind=1;ind<=n;ind++)
            if(ind!=i&&a[ind][p[i]])
              a[ind]^=a[i];
    }
}
int main()
{
    ifstream f("laser.in");
    ofstream g("laser.out");
    f>>n;orig.x=0;orig.y=0;
    for(i=1;i<=n;i++)
    {
        f>>X1>>Y1>>X2>>Y2;
        v[i].x=X1;
        v[i].y=Y1;
        v[i].tip=i;
        v[n+i].x=X2;
        v[n+i].y=Y2;
        v[n+i].tip=i;
    }
    sort(v+1,v+2*n+1,trigo);
    v[2*n+1]=v[1];
    baleiere();
    for(i=1;i<=n;i++)
        {
            f>>ok;
            a[i][k+1]=ok;
        }
    gauss();
    for(i=1;i<=n;i++)
        if(a[i][k+1])
         nr++;
    g<<nr<<'\n';
    for(i=1;i<=n;i++)
        if(a[i][k+1])
          g<<fixed<<setprecision(8)<<unghi[p[i]]<<'\n';
    return 0;
}