Cod sursa(job #2429107)

Utilizator AlexPop28Pop Alex-Nicolae AlexPop28 Data 7 iunie 2019 20:34:15
Problema Laser Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.02 kb
#include <bits/stdc++.h>
#define DEBUG(x) cerr << (#x) << ": " << (x) << '\n'

using namespace std;

struct Point {
  int x, y, id;
};

struct Solver {
  int n;
  vector<int> color;
  vector<vector<pair<int, int>>> adj;
  Solver(int n) : n(n), color(n + 1, -1), adj(n + 1) {}
  void add(int l, int r, int val) {
    adj[l].emplace_back(r, val);
    adj[r].emplace_back(l, val);
  }
  bool dfs(int node, int col) {
    if (color[node] != -1) {
      return color[node] == col;
    }
    color[node] = col;
    bool ret = true;
    for (auto &p : adj[node]) {
      ret &= dfs(p.first, col ^ p.second);
    }
    return ret;
  }
  bool solve() {
    for (int i = 0; i < n; ++i) {
      if (color[i] == -1) {
        if (!dfs(i, 0)) {
          return false;
        }
      }
    }
    return true;
  }
  vector<bool> getSol() {
    vector<bool> sol(n);
    for (int i = 0; i < n; ++i) {
      sol[i] = color[i] ^ color[i + 1];
    }
    return sol;
  }
};

int getQuadrant(Point p) {
  if (p.x >= 0 && p.y >= 0) return 1;
  if (p.x < 0 && p.y >= 0) return 2;
  if (p.x < 0 && p.y < 0) return 3;
  assert(p.x >= 0 && p.y < 0);
  return 4;
}

int det(Point a, Point b, Point c) {
  return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);
}

const long double PI = acos(-1);
long double getAng(Point p) {
  long double ang = atan2(p.y, p.x);
  if (ang < 0) ang += 2 * PI;
  return ang * 180.0 / PI;
}

int main() {
  freopen("laser.in", "r", stdin);
  freopen("laser.out", "w", stdout);
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.precision(8);
  cout << fixed;

  int n;
  cin >> n;
  vector<Point> points(2 * n);
  for (int i = 0; i < n; ++i) {
    int x, y;
    cin >> x >> y;
    points[2 * i] = {x, y, i};
    cin >> x >> y;
    points[2 * i + 1] = {x, y, i};
  }
  vector<int> state(n);
  for (int &x : state) {
    cin >> x;
  }
  sort(points.begin(), points.end(), [&](Point &a, Point &b) {
    int qa = getQuadrant(a);
    int qb = getQuadrant(b);
    if (qa != qb) return qa < qb;
    return det({0, 0, 0}, a, b) > 0;
  });
  
  assert(is_sorted(points.begin(), points.end(), [&](Point &a, Point &b) {
    return getAng(a) < getAng(b);
  }));
  
  for (int it = 0; it < 2; ++it) {
    vector<int> other(n, -1);
    Solver solver(2 * n);
    solver.add(0, 2 * n, it);
    for (int i = 0; i < 2 * n; ++i) {
      if (other[points[i].id] != -1) {
        if (det({0, 0, 0}, points[other[points[i].id]], points[i]) < 0) {
          solver.add(other[points[i].id] + 1, i, state[points[i].id] ^ it);
        } else {
          solver.add(other[points[i].id], i + 1, state[points[i].id]);
        }
      }
      other[points[i].id] = i;
    }
  
    if (solver.solve()) {
      vector<bool> sol = solver.getSol();
      int ans = count(sol.begin(), sol.end(), 1);
      cout << ans << endl;
      for (int i = 0; i < 2 * n; ++i) {
        if (sol[i]) {
          cout << getAng(points[i]) << '\n';
        }
      }
      return 0;
    }
  }
  
  assert(false);

#ifdef LOCAL_DEFINE
  cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
  return 0;
}