Cod sursa(job #2638371)

Utilizator segtreapMihnea Andreescu segtreap Data 27 iulie 2020 23:59:53
Problema Laser Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.21 kb
#include <bits/stdc++.h>

using namespace std;

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

  typedef long double ld;
  const ld PI = (ld) 2 * acos((ld) 0);
  const ld EPS = 1e-3;

  struct T {
    int x1, y1;
    int x2, y2;
  };

  function<ld(ld)> inv = [&] (ld x) {
    return x * PI / 180;
  };

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

  int n;
  cin >> n;
  vector<T> a(n);
  map<ld, int> mp;

  for (int i = 0; i < n; i++) {
    cin >> a[i].x1 >> a[i].y1 >> a[i].x2 >> a[i].y2;
    ld ang1 = get_ang(a[i].x1, a[i].y1), ang2 = get_ang(a[i].x2, a[i].y2), dif;
    if (ang1 > ang2) {
      swap(ang1, ang2);
    }
    dif = ang2 - ang1;
    if (dif <= 180) { /// pre[ang2] ^ pre[ang1 - EPS] ^ col = 0
      mp[ang2] = 0;
      mp[ang1 - EPS] = 0;
    } else { /// pre[ang1] ^ pre[ang2 - EPS] ^ col ^ all = 0
      mp[ang1] = 0;
      mp[ang2 - EPS] = 0;
    }
  }

  vector<ld> all_angs;

  int m = 0;
  for (auto &it : mp) {
    all_angs.push_back(it.first);
    it.second = m++;
  }
  vector<vector<pair<int, int>>> g(m), g2(m);
  vector<int> col(m);

  for (int i = 0; i < n; i++) {
    int col;
    cin >> col;
    ld ang1 = get_ang(a[i].x1, a[i].y1), ang2 = get_ang(a[i].x2, a[i].y2), dif;
    if (ang1 > ang2) {
      swap(ang1, ang2);
    }
    dif = ang2 - ang1;
    if (dif <= 180) { /// pre[ang2] ^ pre[ang1 - EPS] ^ col = 0
      int x = mp[ang2], y = mp[ang1 - EPS];
      g[x].push_back({y, col});
      g[y].push_back({x, col});
    } else { /// pre[ang1] ^ pre[ang2 - EPS] ^ col ^ all = 0
      int x = mp[ang1], y = mp[ang2 - EPS];
      g2[x].push_back({y, col});
      g2[y].push_back({x, col});
    }
  }

  bool error;

  function<void(int, int)> dfs = [&] (int all, int a) {
    if (error) {
      return;
    }

    for (auto &it : g[a]) {
      int b = it.first, x = it.second ^ col[a];
      if (col[b] == -1) {
        col[b] = x;
        dfs(all, b);
      }
      if (col[b] != x) {
        error = 1;
        return;
      }
    }

    for (auto &it : g2[a]) {
      int b = it.first, x = all ^ it.second ^ col[a];
      if (col[b] == -1) {
        col[b] = x;
        dfs(all, b);
      }
      if (col[b] != x) {
        error = 1;
        return;
      }
    }
  };

  for (int all = 0; all <= 1; all++) {
    error = 0;
    for (int i = 0; i < m; i++) {
      col[i] = -1;
    }
    for (int i = 0; i < m; i++) {
      if (col[i] == -1) {
        col[i] = 0;
        dfs(all, i);
      }
    }
    if (error) {
      continue;
    }
    vector<ld> angs;
    for (int i = 1; i < m; i++) {
      if (col[i] != col[i - 1]) {
        angs.push_back(all_angs[i]);
      }
    }
    if ((int) angs.size() % 2 != all) {
      continue;
    }

    /**for (auto &it : angs) {
      cout << "0 0 " << fixed << cos(inv(it)) * 1e3 << " " << sin(inv(it)) * 1e3 << "\n";
    }

    return 0; **/

    cout << (int) angs.size() << "\n";
    for (auto &it : angs) {
      cout << it << "\n";
    }
    cout << "\n";
    return 0;
  }

  while (1) {

  }

  return 0;
}