Cod sursa(job #2638452)

Utilizator segtreapMihnea Andreescu segtreap Data 28 iulie 2020 12:16:35
Problema Laser Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.14 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 EPS = 1e-14;
  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 (ang1 < ang2) {
      return ang1 <= ang && ang <= ang2;
    } else {
      return ang1 <= ang || ang <= ang2;
    }
  };

  int n;
  cin >> n;
  vector<pair<ld, ld>> intervals;
  vector<ld> angs, bisec;

  for (int i = 0; i < n; i++) {
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    ld ang1 = get_ang(x1, y1), ang2 = get_ang(x2, y2);
    if (ang1 > ang2) {
      swap(ang1, ang2);
    }
    angs.push_back(ang1);
    angs.push_back(ang2);
    if (ang2 - ang1 < 180) {
      intervals.push_back({ang1, ang2});
    } else {
      intervals.push_back({ang2, ang1});
    }
  }

  sort(angs.begin(), angs.end());
  for (int i = 0; i < 2 * n - 1; i++) {
    bisec.push_back((angs[i] + angs[i + 1]) * 0.5);
  }
  bisec.push_back((angs[2 * n - 1] + angs[0] + 360) * 0.5);
  if (bisec.back() >= 360) {
    bisec.back() -= 360;
  }
  int m = 2 * n;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      b[i][j] = contain(intervals[i].first, intervals[i].second, angs[j]);
    }
    int x;
    cin >> x;
    if (x) {
      b[i][m] = 1;
    }
  }
  vector<int> pos(n, -1);
  for (int i = 0; i < n; i++) {
    int j = 0;
    while (b[i][j] == 0 && j < m) {
      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(bisec[pos[i]]);
    }
  }
  cout << (int) sol.size() << "\n";
  for (auto &ang : sol) {
    cout << fixed << setprecision(6) << ang << "\n";
  }
  return 0;
}