Cod sursa(job #1302726)

Utilizator paunmatei7FMI Paun Matei paunmatei7 Data 27 decembrie 2014 11:19:49
Problema Laser Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.55 kb
#include <cstdio>
#include <algorithm>
#include <cmath>

#define NMAX 517
#define x first
#define y second
#define Eps 1e-8

using namespace std;

pair < double, double > a[NMAX];
double v[NMAX * 2];
int n, Nr, Ans[NMAX * 2];
int System[NMAX][NMAX * 2];

double unghi(int X, int Y){
    double Angle = atan2(Y, X) * 180.0 / acos(-1);
    if(Angle < 0.0)
        Angle += 360.0;
    return Angle;
}

void Gauss(){
    int i = 1, j = 1;
    while (i <= n && j <= Nr) {
        int k;
        for(k = i; k <= n && !System[k][j]; ++k);
        if(k == n + 1){
            ++j;
            continue;
        }
        swap(System[i], System[k]);
        for(k = 1; k <= n; ++k)
            if(i != k && System[k][j])
                for(int l = 1; l <= Nr + 1; ++l)
                    System[k][l] ^= System[i][l];
        ++i;
        ++j;
    }
}

int main(){
    freopen("laser.in", "r", stdin);
    freopen("laser.out", "w", stdout);
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i){
        int X1, Y1, X2, Y2;
        scanf("%d %d %d %d", &X1, &Y1, &X2, &Y2);
        a[i].x = unghi(X1, Y1);
        a[i].y = unghi(X2, Y2);
        if(a[i].x > a[i].y)
            swap(a[i].x, a[i].y);
    }
    for(int i = 1; i <= n; ++i)
        scanf("%d", &System[i][2 * n + 1]);
    for(int i = 1; i <= n; ++i){
        v[++Nr] = a[i].x;
        v[++Nr] = a[i].y;
    }
    sort(v + 1, v + Nr + 1);
    v[Nr + 1] = v[1] + 360.0;
    for(int i = 1; i <= Nr; ++i)
        v[i] = (double)(v[i] + v[i + 1]) / 2.0;
    ///System
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= Nr; ++j)
            if(a[i].y - a[i].x < 180.0 + Eps){
                if(a[i].x - v[j] < Eps && v[j] - a[i].y < Eps)
                    System[i][j] = 1;
            }
            else
                if(a[i].y - v[j] < Eps || v[j] - a[i].x < Eps)
                    System[i][j] = 1;
    /**for(int i = 1; i <= n; ++i, printf("\n"))
        for(int j = 1; j <= Nr; ++j)
            printf("%d ", System[i][j]);**/
    Gauss();
    /**for(int i = 1; i <= n; ++i, printf("\n"))
        for(int j = 1; j <= Nr; ++j)
            printf("%d ", System[i][j]);**/
    for(int i = 1; i <= n; ++i){
        int j;
        for(j = 1; j <= Nr + 1 && !System[i][j]; ++j);
        if(j <= Nr)
            Ans[j] = System[i][Nr + 1];
    }
    int n = 0;
    for(int i = 1; i <= Nr; ++i)
        n += Ans[i];
    printf("%d\n", n);
    for(int i = 1; i <= Nr; ++i)
        if(Ans[i] == 1)
            printf("%.5f\n", v[i]);
    return 0;
}