Cod sursa(job #3358647)

Utilizator CarenaMironov Cezar Luca Carena Data 18 iunie 2026 21:58:57
Problema Laser Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.99 kb
#include <bits/stdc++.h>
#define fr first
#define sc second

using namespace std;

ifstream in("laser.in");
ofstream out("laser.out");

const int NMAX=520;
const double PI=acos(-1);
int n, poz[2*NMAX];
struct point{double x, y;};
pair<point, point> seg[NMAX];
point endp[2*NMAX];
bitset<2*NMAX> a[NMAX], sol;

bool cmp_arg(const point &p, const point &q)
{
    return atan2(p.y, p.x)<atan2(q.y, q.x);
}

bool intersect(point p, pair<point, point> s)
{
    double k=p.y/p.x;
    double l=(s.sc.y-k*s.sc.x)/(k*s.fr.x-k*s.sc.x-s.fr.y+s.sc.y);
    return (0<l && l<1 && (l*s.fr.x+(1-l)*s.sc.x)*p.x>0);
}

point mid(point p, point q)
{
    if(p.x+q.x==0)
        return {(p.x+2*q.x)/3, (p.y+2*q.y)/3};
    return {(p.x+q.x)/2, (p.y+q.y)/2};
}

void gauss()
{
    for(int j=0;j<2*n;j++)
        poz[j]=-1;
    int i=0, j=0;
    for(;i<n && j<2*n;j++)
    {
        for(int ii=i;a[i][j]==0 && ii<n;ii++)
            if(a[ii][j]==1)
                swap(a[i], a[ii]);
        
        if(a[i][j]==0)
            continue;
        poz[j]=i;
        
        for(int ii=0;ii<n;ii++)
            if(ii!=i && a[ii][j]==1)
                a[ii]^=a[i];
        i++;
    }
    
    for(int j=0;j<2*n;j++)
        if(poz[j]!=-1)
            sol[j]=a[poz[j]][2*n];
}

void afis(point p)
{
    double t=atan2(p.y, p.x);
    if(t<0)
        t=2*PI+t;
    out<<fixed<<setprecision(10)<<t/(2*PI)*360<<'\n';
}

int main()
{
    in>>n;
    for(int i=0;i<n;i++)
    {
        in>>seg[i].fr.x>>seg[i].fr.y>>seg[i].sc.x>>seg[i].sc.y;
        endp[2*i]=seg[i].fr;
        endp[2*i+1]=seg[i].sc;
    }
    
    sort(endp, endp+2*n, cmp_arg);
    point aux=endp[0];
    for(int i=0;i<2*n-1;i++)
        endp[i]=mid(endp[i], endp[i+1]);
    endp[2*n-1]=mid(endp[2*n-1], aux);
    
        
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<2*n;j++)
            a[i][j]=intersect(endp[j], seg[i]);
        a[i][2*n]=1;
    }
    
    gauss();
    out<<sol.count()<<'\n';
    for(int j=0;j<2*n;j++)
        if(sol[j]==1)
            afis(endp[j]);
    return 0;
}