Cod sursa(job #1783344)

Utilizator cella.florescuCella Florescu cella.florescu Data 18 octombrie 2016 22:30:29
Problema Laser Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.19 kb
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 512;
const double PI = acos(-1);

struct Segment {
  double angl1, angl2;
};

int posans[MAXN + 1];
vector <double> cap, bisect, sol;
vector <Segment> seg;
bitset <2 * MAXN + 2> eq[MAXN + 1];

inline double myatan2(int x, int y) {
  double aux = atan2(y, x);
  if (aux < 0.0)
    return aux + 2.0 * PI;
  return aux;
}

bool inters(Segment segm, double angl) {
  bool in = (segm.angl1 <= angl && angl <= segm.angl2);
  if (segm.angl2 - segm.angl1 < PI)
    return in;
  return !in;
}

int main() {
    double a1, a2;
    int n, i, j, k, x1, y1, x2, y2;
    ifstream fin("laser.in");
    fin >> n;
    for (i = 0; i < n; ++i) {
      fin >> x1 >> y1 >> x2 >> y2;
      a1 = myatan2(x1, y1);
      a2 = myatan2(x2, y2);
      if (a1 < a2)
        seg.push_back({a1, a2});
      else
        seg.push_back({a2, a1});
      cap.push_back(a1);
      cap.push_back(a2);
    }
    sort(cap.begin(), cap.end());
    cap.push_back(cap[0] + 2 * PI);
    for (i = 0; i < 2 * n; ++i)
      bisect.push_back((cap[i] + cap[i + 1]) / 2.0);
    if (bisect[2 * n - 1] >= 2 * PI)
      bisect[2 * n - 1] -= 2 * PI;
    sort(bisect.begin(), bisect.end());
    for (i = 0; i < n; ++i) {
      fin >> x1;
      if (x1)
        eq[i].set(2 * n);
    }
    fin.close();
    for (i = 0; i < n; ++i)
      for (j = 0; j < 2 * n; ++j)
        eq[i][j] = inters(seg[i], bisect[j]);
    i = j = 0;
    while (i < n && j < 2 * n) {
      if (eq[i][j] == false) {
        for (k = i + 1; k < n && eq[k][j] == false; ++k) {}
        if (k < n)
          swap(eq[i], eq[k]);
        else {
          ++j;
          continue;
        }
      }
      if (eq[i][j])
        for (k = 0; k < n; ++k)
          if (i != k && eq[k][j])
            eq[k] ^= eq[i];
      posans[i++] = j++;
    }
    for (i = 0; i < n; ++i)
      if (eq[i][2 * n])
        sol.push_back(bisect[posans[i]]);
    sort(sol.begin(), sol.end());
    ofstream fout("laser.out");
    fout << sol.size() << '\n' << setprecision(6) << fixed;
    for (i = 0; i < sol.size(); ++i)
      fout << sol[i] / PI * 180 << '\n';
    fout.close();
    return 0;
}