Cod sursa(job #1955611)

Utilizator Bodo171Bogdan Pop Bodo171 Data 6 aprilie 2017 09:00:26
Problema Laser Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.23 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;
double unghi[2*nmax];
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;
}
bool trigo(point unu,point doi)
{
    return det(orig,unu,doi)>0;
}
double get_angle(double x,double y)
{
    angle=atan2(fabs(y),fabs(x));
    if(x<0&&y>=0) angle=M_PI-angle;
    if(x<=0&&y<0) angle=M_PI+angle;
    if(x>0&&y<0) angle=2*M_PI-angle;
    return (angle/M_PI*conv);
}
void baleiere()
{
    for(i=1;i<=2*n;i++)
    {
        if(current[abs(v[i].tip)]) current[abs(v[i].tip)]=0;
        else current[abs(v[i].tip)]=1;
        if(det(orig,v[i],v[i+1])>=0)
        {
            k++;
            for(j=1;j<=n;j++)
               {a[j][k]=current[j];cout<<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;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;
    for(i=1;i<=n;i++)
    {
        f>>X1>>Y1>>X2>>Y2;
        v[i].x=X1;
        v[i].y=X2;
        v[i].tip=i;
        v[n+i].x=X2;
        v[n+i].y=Y2;
        v[n+i].tip=-i;
        if(det(orig,v[i],v[n+i])<0)
        {
            v[i].tip*=-1;
            v[n+i].tip*=-1;
        }
    }
    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(7)<<unghi[p[i]]<<'\n';
    return 0;
}