Cod sursa(job #2638109)

Utilizator segtreapMihnea Andreescu segtreap Data 26 iulie 2020 22:52:39
Problema Laser Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.01 kb
#include <cstdio>
#include <iostream>
#include <vector>
#include <map>
#include <functional>
#include <cmath>
#include <iomanip>

using namespace std;

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

void print(ld aaa) {
  cout << fixed << 0 << " " << 0 << " " << 1e3 * cos(aaa * PI / 180) << " " << 1e3 * sin(aaa * PI / 180) << "\n";
}


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 rep = [&] (ld x) {
    while (x < 0) {
      x += 360;
    }
    while (x >= 360) {
      x -= 360;
    }
    return x;
  };

  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);

    if (ang1 > ang2) {
      swap(ang1, ang2);
    }
    ld difang = ang2 - ang1;
    if (difang <= 180) {
      mp[ang1 - EPS] = 0;
      mp[ang2] = 0;
    } else {
      mp[ang2 - EPS] = 0;
      mp[ang1 + 360] = 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);
    if (ang1 > ang2) {
      swap(ang1, ang2);
    }
    int x, y, col;
    ld difang = ang2 - ang1;
    if (difang <= 180) {
      x = mp[ang1 - EPS];
      y = mp[ang2];
    } else {
      x = mp[ang2 - EPS];
      y = mp[ang1 + 360];
    }

    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);
    angles.back() = rep(angles.back());
  }

  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]);
    }
  }
  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";
}