Cod sursa(job #2480968)

Utilizator NicolaalexandraNicola Alexandra Mihaela Nicolaalexandra Data 26 octombrie 2019 12:02:08
Problema Laser Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.99 kb
#include <bits/stdc++.h>
#define DIM 2000
using namespace std;

ifstream fin ("laser.in");
ofstream fout ("laser.out");
struct point{
    double x,y;
};
point points[DIM];
struct segment{
    double x,y,x2,y2;
}sgm[DIM];

int a[DIM][DIM],stare[DIM],sol[DIM];
pair <double,double> dr[DIM];
int n,i,j,k;
double X1,Y1,X2,Y2;
vector <double> ans;

inline double get_det (double X1, double Y1, double X2, double Y2, double X3, double Y3){
    return (X2-X1)*(Y3-Y1) - (X3-X1)*(Y2-Y1);
}
inline double dist_org (point a){
    return a.x*a.x + a.y*a.y;
}
inline double get_dist (double x, double y, double x2, double y2){
    return sqrt ((x-x2)*(x-x2) + (y-y2)*(y-y2));
}
inline int cadran (point 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;
}
inline int cmp (point a, point b){
    int nr1 = cadran(a), nr2 = cadran(b);
    if (nr1 != nr2)
        return nr1 < nr2;
    double aria = get_det (0,0,a.x,a.y,b.x,b.y);
    if (aria)
        return aria > 0;
    return dist_org (a) < dist_org (b);
}
inline int intersectie (double x, double y, double x2, double y2, double x3, double y3){
    /// dreapta det de punctele 0,0 si x,y intersecteaza segmentul x2,y2; x3,y3
    if (get_det(0,0,x,y,x2,y2) * get_det(0,0,x,y,x3,y3) < 0 && get_det(x2,y2,x3,y3,0,0) * get_det(x2,y2,x3,y3,x,y) < 0)
        return 1;
    return 0;
}
inline int urm (int x){
    if (x < k)
        return x+1;
    return 1;
}
int main (){

    fin>>n;
    for (i=1;i<=n;i++){
        fin>>X1>>Y1>>X2>>Y2;
        points[++k] = {X1,Y1};
        points[++k] = {X2,Y2};
        sgm[i] = {X1,Y1,X2,Y2};
    }
    /// sortez punctele dupa unghi
    sort (points+1,points+k+1,cmp);
    //for (i=1;i<=k;i++)
       // fout<<points[i].x<<" "<<points[i].y<<"\n";
    /// pt fiecare pereche de puncte consecutive iau bisectoarea

    for (i=1;i<=k;i++){
        point A = points[i], B = points[urm(i)];
        double dist_ob = get_dist (0,0,B.x,B.y);
        double dist_oa = get_dist (0,0,A.x,A.y);
        double dist_ab = get_dist (A.x,A.y,B.x,B.y);
        /// bisectoarea
        double xm = A.x*dist_ob/(dist_ob+dist_oa) + B.x*dist_oa/(dist_ob+dist_oa);
        double ym = A.y*dist_ob/(dist_ob+dist_oa) + B.y*dist_oa/(dist_ob+dist_oa);

        xm *= 10000.0, ym *= 10000.0;

        /// acum vad ce segmente intersecteaza
        dr[i] = make_pair (xm,ym);
        for (int j=1;j<=n;j++){
            if (intersectie (xm,ym,sgm[j].x,sgm[j].y,sgm[j].x2,sgm[j].y2))
                a[j][i] = 1;
        }}

    for (i=1;i<=n;i++){
        fin>>stare[i];
        a[i][k+1] = stare[i];
    }

    /*for (i=1;i<=n;i++,fout<<"\n")
        for (j=1;j<=k+1;j++)
            fout<<a[i][j]<<" ";*/
    /// gauss
    int i = 1, j = 1, m = k;
    while (i <= n && j <= m){
        int lin = i;
        while (lin <= n && !a[lin][j])
            lin++;
        if (lin == n+1){
            j++;
            continue;
        }
        if (i != lin){
            for (k=1;k<=m+1;k++)
                swap (a[i][k],a[lin][k]);
        }
        for (k=i+1;k<=n;k++){
            if (a[k][j]){
                for (int t=1;t<=m+1;t++)
                    a[k][t] ^= a[i][j];
            }}
        i++, j++;
    }
    for (i=n;i;i--){
        j = 1;
        while (j <= m+1 && !a[i][j])
            j++;
        if (j == m+2)
            continue;
        sol[j] = a[i][m+1];
        for (k=j+1;k<=m;k++)
            sol[j] ^= (a[i][k]*sol[k]);
    }
    for (i=1;i<=m;i++)
        if (sol[i]){
            /// inseamna ca aleg dreapta asta
            double val = atan2 (dr[i].second,dr[i].first);
            if (val < 0)
                val += 2*3.14159265;
            val = val*180 / 3.14159265;
            ans.push_back(val);
        }
    fout<<ans.size()<<"\n";
    for (int i=0;i<ans.size();i++)
        fout<<setprecision(6)<<fixed<<ans[i]<<"\n";

    return 0;
}