Cod sursa(job #2638106)

Utilizator segtreapMihnea Andreescu segtreap Data 26 iulie 2020 21:51:57
Problema Laser Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.2 kb
#include <cstdio>
#include <iostream>
#include <vector>
#include <map>
#include <functional>
#include <cmath>

using namespace std;




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

  typedef long double ld;
  const ld PI = 2.0 * acos(0.0);

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

  auto inv = [&] (ld ang) {
    return ang * PI / 180;
  };

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

  int n;
  scanf("%d", &n);
  vector<T> v(n);
  map<ld, int> mp;

  for (int i = 0; i < n; i++) {
    scanf("%d %d %d %d", &v[i].x1, &v[i].y1, &v[i].x2, &v[i].y2);

    ld ang1 = get_ang(v[i].x1, v[i].y1);
    ld ang2 = get_ang(v[i].x2, v[i].y2);
    mp[ang1] = 0;
    mp[ang2] = 0;
  }

  int ini = n;

  n = 0;
  for (auto &it : mp) {
    it.second = n++;
  }


  vector<vector<pair<int, int>>> g(n);
  vector<int> what(n, -1);

  for (int i = 0; i < ini; i++) {
    ld ang1 = get_ang(v[i].x1, v[i].y1);
    ld ang2 = get_ang(v[i].x2, v[i].y2);
    int x = mp[ang1], y = mp[ang2], col;
    scanf("%d", &col);
    g[x].push_back({y, col});
    g[y].push_back({x, col});
  }

  function<void(int)> dfs = [&](int a) {
    for (auto &it : g[a]) {
      int b = it.first;
      int c = it.second;
      if (what[b] == -1) {
        what[b] = c ^ what[a];
        dfs(b);
      }
      if (what[b] != (c ^ what[a])) {
        cout << "error on dfs\n";
        return 0;
      }
    }
  };

  for (int i = 0; i < n; i++) {
    if (what[i] == -1) {
      what[i] = 0;
      dfs(i);
    }
  }
  vector<ld> angles;
  for (auto &it : mp) {
    angles.push_back(it.first);
  }

  int cnt = 0;

  for (int i = 1; i < n; i++) {
    if (what[i] != what[i - 1]) {
      cnt++;
    }
  }


  printf("%d\n", cnt);
  for (int i = 1; i < n; i++) {
    if (what[i] != what[i - 1]) {
      printf("%.7lf\n", angles[i] - 0.0001);
    }
  }
  return 0;

  for (int i = 0; i < n; i++) {
    cout << angles[i] << " ";
  }
  cout << "\n";

  for (int i = 0; i < n; i++) {
    cout << what[i] << " ";
  }
  cout << "\n";
}