Cod sursa(job #2482596)

Utilizator Ruxandra985Nanu Ruxandra Laura Ruxandra985 Data 28 octombrie 2019 17:20:51
Problema Laser Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 5.61 kb
#include <bits/stdc++.h>
#define DIMN 600
using namespace std;
struct punct {
    long double x , y;
} e[2*DIMN] , origine , bis[2*DIMN];

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

int a[DIMN][2*DIMN],dp[2*DIMN];

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 ) / acos(-1);
    return 180.0 + ( atan2(-1.0 * x.y , -1.0 * x.x) * 180.0 ) / acos(-1) ;

}
long double det (long double x1,long double y1,long double x2,long double y2,long double x3,long double y3 ){
    return (x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1);
}
int cmp (punct a,punct b){ /// return 1 = ordinea buna
    return det(0.0 , 0.0 , a.x , a.y , b.x , b.y) > 0;
}
int segm (long double x3,long double y3,long double x1,long double y1 , long double x2 , long double y2){
    long double 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 ((x3 - x1) * (x3 - x2) < 0 || (y3 - y1) * (y3 - y2) < 0)
        return 1;
    return 0;
}
int intersectie_segmente (long double x1,long double y1,long double x2,long double y2,long double x3,long double y3,long double x4,long double y4){
    long double 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;

}
long double dist (long double x1,long double y1,long double x2,long double y2){
    return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
}
int intersectie (punct p1 , punct p2 , punct q1 , punct q2){
    return intersectie_segmente (0.0,0.0, 20000.0 * p2.x , 20000.0 * 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;
    long double x1,y1,x2,y2;
    long double d1,d2;
    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++){

            d1 = dist(0,0,e[i].x,e[i].y);
            d2 = dist(0,0,e[i+1].x,e[i+1].y);

            long double xb = e[i].x * d2 / (d2 + d1) + e[i+1].x * d1 / (d1 + d2);
            long double yb = e[i].y * d2 / (d2 + d1) + e[i+1].y * d1 / (d1 + d2);

            bis[i].x = xb;
            bis[i].y = yb;

            xb*=10000.0;
            yb*=10000.0;

            /// 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]
            fout << setprecision(6) << fixed << degrees(bis[i]) << "\n";
            /*if (i!=2*n){
                l = degrees (e[i]);
                r = degrees (e[i+1]);

            }
            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;
}