Cod sursa(job #2530366)

Utilizator bogdi1bogdan bancuta bogdi1 Data 24 ianuarie 2020 18:23:36
Problema Laser Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.48 kb
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const double eps = 1.e-6;
const double PI = 3.141592653;
struct Points
{
    double 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 (P1.x-P3.x)*(P2.y-P3.y)-(P1.y-P3.y)*(P2.x-P3.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(a, b, {0, 0})<0;
}
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("%lf%lf%lf%lf", &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);
    v[2*n+1]=v[1];
    for(i=1; i<=2*n; i++){
        v[i].x=((v[i].x+v[i+1].x)/2.0);
        v[i].y=((v[i].y+v[i+1].y)/2.0);
        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;
}