Cod sursa(job #2530323)

Utilizator bogdi1bogdan bancuta bogdi1 Data 24 ianuarie 2020 17:52:12
Problema Laser Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.37 kb
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const double eps = 1.e-6;
const double PI = 3.14159265;
struct Points
{
    int x,y;
};
Points v[1030];
int mat[1030][1030];
struct Line
{
    Points a;
    Points b;
} lines[1030];
struct Solutie
{
    bool ok;
    double angle;
} sol[1030];
double crossproduct(Points P1, Points P2, Points P3)
{
    return (P2.x-P1.x)*(P3.y-P2.y)-(P2.y-P1.y)*(P3.x-P2.x);
}
int ccw(Points P1, Points P2, Points P3)
{
    double cp;
    cp=crossproduct(P1,P2,P3);
    if(fabs(cp)<eps)
      return 0;
    else{
      if(cp>=eps)
        return 1;
      else
        return -1;
    }
}
bool cmp(Points a, Points b)
{
    int cad1,cad2;
    if(a.x>=0 && a.y>=0)
        cad1=1;
    if(a.x>=0 && a.y<0)
        cad1=4;
    if(a.x<0 && a.y<0)
        cad1=3;
    if(a.x<0 && a.y>=0)
        cad1=2;
    if(b.x>=0 && b.y>=0)
        cad2=1;
    if(b.x>=0 && b.y<0)
        cad2=4;
    if(b.x<0 && b.y<0)
        cad2=3;
    if(b.x<0 && b.y>=0)
        cad2=2;
    if(cad1!=cad2)
        return cad1<cad2;
    return ccw({0, 0}, a, b)!=1;
}
bool intersect(Points A, Points B, Points C, Points D)
{
    Points pos;
    double a1=B.y-A.y;
    double b1=A.x-B.x;
    double c1=a1*A.x+b1*A.y;
    double a2=D.y-C.y;
    double b2=C.x-D.x;
    double c2=a2*C.x+b2*C.y;
    double det=a1*b2-a2*b1;
    if(det==0)
        return 0;
    pos.x=(b2*c1-b1*c2)/det;
    pos.y=(a1*c2-a2*c1)/det;
    if(min(C.x, D.x)<=pos.x && pos.x<=max(C.x, D.x) && min(C.y, D.y)<=pos.y && pos.y<=max(C.y, D.y))
        if(pos.x*B.x>=eps && pos.y*B.y>=eps)
            return 1;
    return 0;
}
int main()
{   freopen("laser.in", "r", stdin);
    freopen("laser.out", "w", stdout);
    int n,i,x,j,k,l,ans=0;
    scanf("%d", &n);
    for(i=1; i<=n; i++){
        scanf("%d%d%d%d", &lines[i].a.x, &lines[i].a.y, &lines[i].b.x, &lines[i].b.y);
        v[2*i-1]=lines[i].a;
        v[2*i]=lines[i].b;
    }
    for(i=1; i<=n; i++){
        scanf("%d", &x);
        mat[i][2*n+1]=x;
    }
    sort(v+1, v+2*n+1,cmp);
    for(i=1; i<=2*n; i++){
        sol[i].angle=atan2(v[i].y, v[i].x)*180/PI;
        sol[i].angle+=360.0;
        if(sol[i].angle-360.0>eps)
            sol[i].angle-=360.0;
        for(j=1; j<=n; j++)
            if(intersect({0, 0}, v[i], lines[j].a, lines[j].b)==1)
                mat[j][i]=1;
    }
    for(i=1,j=1; i<=n && j<=2*n; i++,j++){
        for(k=i; k<=n; k++){
            if(mat[k][j]!=0){
                for(l=1; l<=2*n+1; l++)
                    swap(mat[k][l], mat[i][l]);
                break;
            }
        }
        if(mat[i][j]==0){
            i--;
            continue;
        }
        for(k=i+1; k<=n; k++){
            if(mat[k][j]!=0){
            for(l=j+1; l<=2*n+1; l++)
                mat[k][l]=(mat[k][l]+mat[i][l])%2;
            mat[k][j]=0;
            }
        }
    }
    for(i=n; i>=0; i--)
        for(j=1; j<=2*n+1; j++){
            if(mat[i][j]!=0){
                sol[j].ok=mat[i][2*n+1];
                for(l=j+1; l<=2*n; l++)
                    sol[j].ok=(sol[j].ok+mat[i][l]*sol[l].ok)%2;
                ans+=sol[j].ok;
                break;
            }
        }
    printf("%d\n", ans);
    for(i=1; i<=2*n; i++)
        if(sol[i].ok==1)
            printf("%.6lf\n", sol[i].angle);
    return 0;
}