Cod sursa(job #2482571)

Utilizator Ruxandra985Nanu Ruxandra Laura Ruxandra985 Data 28 octombrie 2019 16:09:27
Problema Laser Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.92 kb
#include <bits/stdc++.h>
#define DIMN 600
using namespace std;
struct punct {
    int x , y;
} e[2*DIMN] , origine;

struct idk{
    punct fst,scd;
} v[DIMN];

int a[DIMN][2*DIMN],dp[2*DIMN];
long double PI = 3.14159265359;
int cadran (punct a){
    if (a.x>=0 && a.y>=0)
        return 1;
    if (a.x<=0 && a.y>=0)
        return 2;
    if (a.x<0 && a.y<=0)
        return 3;
    return 4;
}
long double degrees (punct x){ /// cate grade (0..360) de la 0 0 la x

    if (cadran(x) <= 2)
        return ( atan2(1.0 * x.y , 1.0 * x.x) * 180.0 ) / PI;
    return 180.0 + ( atan2(-1.0 * x.y , -1.0 * x.x) * 180.0 ) / PI ;

}
long long det (int x1,int y1,int x2,int y2,int x3,int y3 ){
    return 1LL * (x2 - x1) * (y3 - y1) - 1LL * (x3 - x1) * (y2 - y1);
}
int cmp (punct a,punct b){ /// return 1 = ordinea buna
    return det(0 , 0 , a.x , a.y , b.x , b.y) > 0;
}
/*int segm (int x3,int y3,int x1,int y1 , int x2 , int y2){
    long long d = det (x1,y1,x2,y2,x3,y3);
    if (d!=0)
        return 0;
    if (x1 == x3 && y1 == y3)
        return 1;
    if (x2 == x3 && y2 == y3)
        return 1;
    if (1LL * (x3 - x1) * (x3 - x2) < 0 || 1LL * (y3 - y1) * (y3 - y2) < 0)
        return 1;
    return 0;
}*/
int intersectie_segmente (int x1,int y1,int x2,int y2,int x3,int y3,int x4,int y4){
    long long d1,d2,d3,d4;

   // if (segm (x1,y1,x3,y3,x4,y4) || segm (x2,y2,x3,y3,x4,y4)  || segm (x3,y3,x1,y1,x2,y2) || segm (x4,y4,x1,y1,x2,y2))
    //    return 1;

    d1 = det (x3,y3,x4,y4,x1,y1);
    d2 = det (x3,y3,x4,y4,x2,y2);
    d3 = det (x1,y1,x2,y2,x3,y3);
    d4 = det (x1,y1,x2,y2,x4,y4);

    if (d1 * d2 < 0 && d3 * d4 < 0)
        return 1;

    return 0;

}
int intersectie (punct p1 , punct p2 , punct q1 , punct q2){
    return intersectie_segmente (0,0, 10000 * p2.x , 10000 * p2.y , q1.x , q1.y , q2.x , q2.y );
}
int main()
{
    ifstream fin ("laser.in");
    ofstream fout ("laser.out");
    int n,i,ev=0,nr,j,k,aux,x1,y1,x2,y2;
    long double l , r;
    fin >> n;
    for (i=1;i<=n;i++){
        fin >> x1 >> y1 >> x2 >> y2;

        ev++;
        e[ev].x = x1;
        e[ev].y = y1;
        ev++;
        e[ev].x = x2;
        e[ev].y = y2;

        v[i].fst.x = x1;
        v[i].scd.x = x2;
        v[i].fst.y = y1;
        v[i].scd.y = y2;

    }
    for (i=1;i<=n;i++)
        fin>>a[i][2*n+1];
    sort (e + 1 , e + ev + 1 , cmp); /// sort unghi
    e[ev+1] = e[1];
    for (i=1;i<=ev;i++){
        /// ce drepte sunt in bucata asta
        for (j=1;j<=n;j++){
            /// ca bis sa intersecteaze segm j , ambele semidrepte
            /// O -> e[i] si O -> e[i+1] trb sa intersecteze segmentul
            if (intersectie(origine , e[i] , v[j].fst , v[j].scd) && intersectie(origine , e[i+1] , v[j].fst , v[j].scd) ){
                a[j][i] = 1;
            }
        }
    }
    /*for (i=1;i<=n;i++){
        for (j=1;j<=2*n+1;j++){
            printf ("%d ",a[i][j]);
        }
        printf ("\n");
    }*/
    /// a[j][i] = 1 -> bisectoarea i intersecteaza segmentul i

    /// am construit matricea de coeficienti
    /// solve gauss

    i=j=1;

    while (i<=n && j<=2*n){
        for (k=i;k<=n;k++){
            if (a[k][j]!=0)
                break;
        }
        if (k>n){ /// variabila libera
            j++;
        }
        else {
            /// interschimb linia i cu k
            for (aux = 1; aux <= 2*n+1; aux++)
                swap(a[i][aux] , a[k][aux]);

            /// stii ca a[i][j] = 1

            for (k=i+1;k<=n;k++){
                if (a[k][j] == 1){
                    for (aux=2*n+1;aux;aux--)
                        a[k][aux] = (a[k][aux] ^ a[i][aux]);
                }
            }
            i++;
            j++;
        }
    }
    /// ai facut sistemul sa devina un triunghi intors
    nr = 0;
    for (i=n;i;i--){
        for (j=1;j<=2*n+1;j++){
            if (a[i][j]!=0) /// nu e 0
                break;
        }

        if (j == 2 * n + 2 )
            continue; /// liber

        dp[j] = a[i][2*n+1]; /// dp[j] => trag sau nu la poz j
        for (aux = j + 1 ; aux <= 2 * n ; aux++){
            dp[j] = (dp[j] ^ (dp[aux] * a[i][aux]));
        }
        nr+=dp[j];
    }
    fout << nr << "\n";
    for (i=1;i<=2*n;i++){
        if (dp[i]){ /// TREBUIE SA IEI IN CALCUL BISECTOAREA UNGHIULUI E[I] -> E[I+1]
            if (i!=2*n){
                l = degrees (e[i]);
                r = degrees (e[i+1]);
                fout << setprecision(6) << fixed << (r + l)/2.0 << "\n";
            }
            else {
                l = degrees (e[1]);
                r =  - (360.0 - degrees (e[2*n]));
                if ((r + l) / 2.0 < 0)
                    fout << setprecision(6) << fixed << ( 360.0 + (r + l) / 2.0 ) << "\n";
                else fout << setprecision(6) << fixed << ( (r + l) / 2.0 ) << "\n";
            }
        }
    }

    return 0;
}