Cod sursa(job #587721)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 5 mai 2011 18:37:56
Problema Laser Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.21 kb
#include <cstdio>
#include <cmath>

using namespace std;

const int N = 520;

int n, s[N], xs[N], ys[N], xf[N], yf[N];

void read() {
  scanf("%d", &n);

  for (int i = 1; i <= n; ++ i)
    scanf("%d%d%d%d", &xs[i], &ys[i], &xf[i], &yf[i]);

  for (int i = 1; i <= n; ++ i)
    scanf("%d", &s[i]);
}

double angle(int x, int y) {
  double a = asin((double)y / sqrt((double)x * x + y * y)) / M_PI * 180;

  if (x >= 0 && y >= 0)
    return a;

  if (x <= 0 && y >= 0)
    return (double)180 - a;
  
  if (x <= 0 && y <= 0)
    return (double)180 - a;

  return (double)360 + a;
}

double u1[N], u2[N], v[2 * N];

int lv;

#include <algorithm>

void angles() {
  for (int i = 1; i <= n; ++ i) {
    u1[i] = v[++ lv] = angle(xs[i], ys[i]);
    u2[i] = v[++ lv] = angle(xf[i], yf[i]);
    if (u1[i] > u2[i])
      swap(u1[i], u2[i]);
  }
}

#include <bitset>

bitset <2 * N> g[N];

bool inters(double x1, double x2, double x3) {
  if (x2 - x1 > 360 - x2 + x1) {
    if ((x3 >= x2 && x3 <= 360) || (x3 >= 0 && x3 <= x1))
      return 1;
    return 0;
  }

  if (x3 >= x1 && x3 <= x2)
    return 1;
  return 0;
}

int m;

void init_gauss() {
  m = 2 * n;

  for (int i = 1; i <= n; ++ i) {
    for (int j = 1; j <= m; ++ j)
      if (inters(u1[i], u2[i], v[j]))
        g[i][j] = 1;
    g[i][0] = s[i];
  }
}

bool used[2 * N];

int line[2 * N];

void gauss() {
  bitset <2 * N> aux;

  for (int c = 1, r = 1; c <= m; ++ c) {
    int raux = 0;
    
    for (raux = r; raux <= n; ++ raux)
      if (g[raux][c])
        break;

    if (raux == n + 1)
      continue;

    if (raux != r) {
      aux = g[r];
      g[r] = g[raux];
      g[raux] = aux;
    }

    for (int i = r + 1; i <= n; ++ i)
        if (g[i][c])
          g[i] ^= g[r];
    
    line[c] = r ++;
  }

  int nru = 0;

  for (int c = m; c >= 0; -- c) {
    if (! line[c])
      continue;
    
    used[c] = g[line[c]][0];
    
    for (int i = c + 1; i <= m; ++ i)
      used[c] ^= g[line[c]][i] & used[i];

    if (used[c])
      ++ nru;
  }

  printf("%d\n", nru);

  for (int i = 1; i <= m; ++ i)
    if (used[i])
      printf("%lf\n", v[i]);
}

int main() {
  freopen("laser.in", "r", stdin);
  freopen("laser.out", "w", stdout);

  read();
  angles();
  init_gauss();
  gauss();

  return 0;
}