Cod sursa(job #2638457)

Utilizator segtreapMihnea Andreescu segtreap Data 28 iulie 2020 12:36:34
Problema Laser Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.04 kb
#include <bits/stdc++.h>

using namespace std;

bitset<1234> b[1234];

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

  typedef long double ld;
  const ld PI = (ld) 2 * acos((ld) 0);

  function<ld(ld, ld)> get_ang = [&] (ld x, ld y) {
    x = atan2(y, x) * 180 / PI;
    if (x < 0) {
      x += 360;
    }
    return x;
  };

  function<bool(ld, ld, ld)> contain = [&] (ld ang1, ld ang2, ld ang) {
    if (ang2 - ang1 > 180) {
      return (ang < ang1 || ang > ang2);
    } else {
      return (ang1 < ang && ang < ang2);
    }
  };

  vector<ld> all, bisecs;
  vector<pair<ld, ld>> pair_angs;
  int n, m;
  cin >> n;
  m = 2 * n;
  for (int i = 0; i < n; i++) {
    int x1, y1, x2, y2;
    ld ang1, ang2;
    cin >> x1 >> y1 >> x2 >> y2;
    ang1 = get_ang(x1, y1);
    ang2 = get_ang(x2, y2);
    if (ang1 > ang2) {
      swap(ang1, ang2);
    }
    pair_angs.push_back({ang1, ang2});
    all.push_back(ang1);
    all.push_back(ang2);
  }

  sort(all.begin(), all.end());

  for (int i = 0; i < m - 1; i++) {
    bisecs.push_back((all[i] + all[i + 1]) * (ld) 0.5);
  }
  bisecs.push_back((360 + all[0] + all[2 * m - 1]) * (ld) 0.5);
  if (bisecs.back() >= 360) {
    bisecs.back() -= 360;
  }

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      b[i][j] = contain(pair_angs[i].first, pair_angs[i].second, bisecs[j]);
    }
    int x;
    cin >> x;
    b[i][m] = x;
  }

  vector<int> pos(n, -1);

  for (int i = 0; i < n; i++) {
    int j = 0;
    while (j < m && b[i][j] == 0) {
      j++;
    }
    if (j == m) {
      continue;
    }
    pos[i] = j;
    for (int k = 0; k < n; k++) {
      if (k != i && b[k][j]) {
        b[k] ^= b[i];
      }
    }
  }

  vector<ld> sol;
  for (int i = 0; i < n; i++) {
    if (pos[i] != -1 && b[i][m]) {
      sol.push_back(bisecs[pos[i]]);
    }
  }

  cout << (int) sol.size() << "\n";
  for (auto &ang : sol) {
    cout << fixed << setprecision(10) << ang << "\n";
  }
  return 0;
}