Cod sursa(job #940447)

Utilizator rudarelLup Ionut rudarel Data 16 aprilie 2013 11:29:44
Problema Laser Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.22 kb
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <bitset>
using namespace std;
 
#define NMAX 550
#define eps 1e-6
#define DIST 30000
 
const double pi = acos(-1);
 
int N;
 
double xx[NMAX];
double yy[NMAX];
double xx1[NMAX];
double yy1[NMAX];
 
int nunghi;
double unghi[NMAX * 2];
 
int nrez;
double rez[NMAX * 2];
 
int jeg[NMAX];
 
bitset <2 * NMAX> a[NMAX];
 
inline double DABS(double x) { return (x < 0) ? -x : x; }
 
inline int semn(double x, double y, double x1, double y1, double x2, double y2)
{
    double q = x * (y1 - y2) - y * (x1 - x2) + x1 * y2 - y1 * x2;
     
    if (DABS(q) < eps) return 0;
    if (q < 0) return -1;
    return 1;
}
 
void make_bitset(int q, double unghi)
{
    double sn = sin(unghi), cs = cos(unghi);
 
    double x = DIST * cs, y = DIST * sn;
 
    int e1, e2;
 
    for (int i = 1; i <= N; i++) {
        e1 = semn(0, 0, xx[i], yy[i], xx1[i], yy1[i]) * semn(x, y, xx[i], yy[i], xx1[i], yy1[i]);
        e2 = semn(xx[i], yy[i], 0, 0, x, y) * semn(xx1[i], yy1[i], 0, 0, x, y);
 
        if (e1 == 1 || e2 == 1) continue;
 
        a[i][q] = 1;
    }
}
 
int main()
{
    int i, x, y, x1, y1;
    double u1, u2;
     
    freopen("laser.in", "r", stdin);
    freopen("laser.out", "w", stdout);
 
    scanf("%d", &N);
 
    for (i = 1; i <= N; i++) {
        scanf("%d %d %d %d", &x, &y, &x1, &y1);
        xx[i] = x; yy[i] = y;
        xx1[i] = x1; yy1[i] = y1;
 
        u1 = atan2(y, x); if (y < 0) u1 += 2 * pi;
        u2 = atan2(y1, x1); if (y1 < 0) u2 += 2 * pi;
 
        unghi[++nunghi] = u1;
        unghi[++nunghi] = u2;
 
//      printf("%lf %lf\n", u1, u2);
    }
//  printf("\n");
 
    sort(unghi + 1, unghi + nunghi + 1);
 
    unghi[nunghi + 1] = -unghi[nunghi];
 
    for (i = 1; i <= nunghi; i++) make_bitset(i, ( unghi[i] + unghi[i + 1] ) * 0.5);
 
//  for (i = 1; i <= nunghi; i++) printf("%lf (%g, %g) | ", (unghi[i] + unghi[i+1]) * 0.5, unghi[i], unghi[i+1]);
//  printf("\n");
         
    int w, k, j;
    for (i = 1; i <= N; i++) {
        scanf("%d", &w);
        a[i][2 * N + 1] = w;
    }
     
/*  for (i = 1; i <= N; i++) {
        for (j = 1; j <= 2 * N + 1; j++) printf("%d ", a[i][j] == 1);
        printf("\n");
    }
    printf("\n");
*/
    bitset <2 * NMAX> aux;
     
    for (i = 1, j = 1; i <= 2 * N && j <= N; i++) {
        for (k = j; k <= N && !a[k][i]; k++);
 
        if (k == N + 1) continue;
 
        aux = a[j];
        a[j] = a[k];
        a[k] = aux;
 
        for (k = 1; k <= N; k++) {
            if (k == j || !a[k][i]) continue;
 
            a[k] ^= a[j];
        }
 
/*      for (int ii = 1; ii <= N; ii++) {
            for (int jj = 1; jj <= 2 * N + 1; jj++) printf("%d ", a[ii][jj] == 1);
            printf("\n");
        }
        printf("\n");
*/
 
        jeg[++jeg[0]] = i;
         
        j++;
    }
 
    int q;
    for (i = 1; i <= jeg[0]; i++) {
        q = jeg[i];
//      printf("-- %d\n", q);
        if (a[i][2 * N + 1]) rez[++nrez] = (unghi[q] + unghi[q + 1]) * 0.5;
    }
 
    printf("%d\n", nrez);
    for (i = 1; i <= nrez; i++) printf("%lf\n", rez[i] / pi * 180);
 
fclose(stdin);
fclose(stdout);
return 0;
}