Cod sursa(job #2690467)

Utilizator retrogradLucian Bicsi retrograd Data 24 decembrie 2020 01:50:10
Problema Laser Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.89 kb
#include <bits/stdc++.h>

using namespace std;
using Point = complex<long long>;
const double PI = 4.0 * atan(1.0);

long long cross(Point a, Point b) { 
  return (conj(a) * b).imag(); 
}
Point perp(Point p) { return {-p.imag(), p.real()}; }

struct Angle : Point {
  int t = 0;
  Angle(Point p = {}, int t = 0) : Point(p), t(t) {}
  int half() const {
    auto x = real(), y = imag(); 
    assert(x || y);
    return y < 0 || (y == 0 && x < 0);
  } 
  Angle t90() const { 
    return {perp(*this), t + (half() && real() >= 0)}; }
	Angle t180() const { return {-(*this), t + half()}; }
	Angle t360() const { return {(*this), t + 1}; }
};

bool operator<(const Angle& a, const Angle& b) {
  if (a.t != b.t) return a.t < b.t;
  if (a.half() != b.half()) return a.half() < b.half();
  return cross(a, b) > 0;
}
bool operator==(Angle a, Angle b) {
  return a.t == b.t && cross(a, b) == 0;
}

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

Angle add(Angle a, Point b) { // where b is a vector
  Angle r(a + b, a.t);
  if (a.t180() < r) r.t--;
  return r.t180() < a ? r.t360() : r;
}
Angle diff(Angle a, Angle b) { // angle b - angle a
	int tu = b.t - a.t; a.t = b.t;
	return {conj(a) * b, tu - (b < a)};
}

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(Point{x1, y1});
    Angle a2(Point{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) {
    a.t = 0;
    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];

  for (int s = 0; s < 2; ++s) {
    DSU D(2 * angs.size() + 2);
    bool fail = false;
    D.Union(0, (2 * n) ^ s);
    D.Union(1, (2 * n) ^ s ^ 1); 
    for (int i = 0; i < n; ++i) {
      auto add = [&](int a, int b, int c) {
        D.Union(2 * a, (2 * b) ^ c);
        D.Union(2 * a + 1, (2 * b) ^ c ^ 1);
      };
      if (l[i] <= r[i]) 
        add(l[i], r[i], v[i]);
      else
        add(r[i], l[i], v[i] ^ s);
      if (D.Find(2 * l[i]) == D.Find(2 * l[i] + 1)) {
        fail = true;
        break;
      }
    }

    if (fail) continue;

    vector<double> ans;
    vector<bool> sol(angs.size() + 1, s);
    for (int i = (int)angs.size(); 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 < (int)angs.size(); ++i) {
      if (sol[i + 1] == sol[i]) continue;
      double a1 = atan2(angs[i].imag(), angs[i].real()), 
             a2 = atan2(angs[(i + 1) % angs.size()].imag(),
                 angs[(i + 1) % angs.size()].real());
      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);
}