Cod sursa(job #2690470)

Utilizator retrogradLucian Bicsi retrograd Data 24 decembrie 2020 02:06:29
Problema Laser Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.98 kb
#include <bits/stdc++.h>

using namespace std;
const double PI = 4.0 * atan(1.0);

struct Angle {
  int x = 0, y = 0, t = 0;
  int half() const {
    assert(x || y);
    return y < 0 || (y == 0 && x < 0);
  } 
	Angle t180() const { return {-x, -y, t + half()}; }
};

bool operator<(const Angle& a, const Angle& b) {
  return make_tuple(a.t, a.half(), a.y * b.x)
    < make_tuple(b.t, b.half(), b.y * a.x);
}
bool operator==(Angle a, Angle b) {
  return a.t == b.t && a.half() == b.half() && a.x * b.y == a.y * b.x;
}

pair<Angle, Angle> SegmentAngles(Angle a, Angle b) {
  if (b < a) swap(a, b);
  if (b < a.t180()) swap(a, b);
  return {a, b};
}

struct DSU {
  vector<int> link;
  DSU(int n) : link(n, -1) {}
  int Find(int x) {
    if (link[x] == -1) return x;
    return link[x] = Find(link[x]);
  }
  bool Union(int a, int b) {
    a = Find(a); b = Find(b);
    if (a == b) return false;
    if (a > b) swap(a, b);
    link[a] = b; return true;
  }
};

int main() {
  ifstream cin("laser.in");
  ofstream cout("laser.out");

  int n; cin >> n;

  vector<Angle> angs(2 * n);
  vector<pair<Angle, Angle>> segs(n);

  for (int i = 0; i < n; ++i) {
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    Angle a1{x1, y1};
    Angle a2{x2, y2};

    segs[i] = SegmentAngles(a1, a2);
    angs[2 * i + 0] = a1;
    angs[2 * i + 1] = a2;
  }

  sort(angs.begin(), angs.end());
  angs.erase(unique(angs.begin(), angs.end()), angs.end());

  auto get = [&](Angle a) {
    auto it = lower_bound(angs.begin(), angs.end(), a);
    assert(it != angs.end() && *it == a);
    return it - angs.begin();
  };

  vector<int> l(n), r(n), v(n);
  for (int i = 0; i < n; ++i) {
    l[i] = get(segs[i].first);
    r[i] = get(segs[i].second);
  }
  for (int i = 0; i < n; ++i)
    cin >> v[i];
  
  int m = angs.size();
  for (int s = 0; s < 2; ++s) {
    DSU D(2 * m + 2);
    bool fail = false;
    auto add = [&](int a, int b, int c) {
      D.Union(2 * a, (2 * b) ^ c);
      D.Union(2 * a + 1, (2 * b) ^ c ^ 1);
      fail |= (D.Find(2 * a) == D.Find(2 * a + 1));
    };
    add(0, m, s);
    for (int i = 0; i < n; ++i) 
      add(l[i], r[i], v[i] ^ (l[i] <= r[i] ? 0 : s));

    if (fail) continue;

    vector<double> ans;
    vector<bool> sol(m + 1, s);
    for (int i = m; i >= 0; --i) {
      int rt = D.Find(2 * i);
      if (rt != 2 * i) 
        sol[i] = (sol[rt / 2] ^ (rt % 2));
    }

    assert(sol[0] == 0);

    for (int i = 0; i < m; ++i) {
      if (sol[i + 1] == sol[i]) continue;
      double a1 = atan2(angs[i].y, angs[i].x), 
             a2 = atan2(angs[(i + 1) % m].y, angs[(i + 1) % m].x);
      double da = a2 - a1; 
      while (da > 2 * PI) da -= 2 * PI;
      while (da < 0) da += 2 * PI;
      double ang = a1 + da / 2;
      ang = ang * 180 / PI;
      while (ang < 0) ang += 360;
      while (ang > 360) ang -= 360;
      ans.push_back(ang);
    }
    sort(ans.begin(), ans.end());
    cout << ans.size() << '\n';
    cout << fixed << setprecision(6);
    for (auto x : ans) cout << x << "\n";

    return 0;
  }
  assert(false);
}