Cod sursa(job #2426501)

Utilizator AlexPop28Pop Alex-Nicolae AlexPop28 Data 28 mai 2019 13:55:51
Problema Laser Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.04 kb
#include <bits/stdc++.h>
#define all(cont) cont.begin(), cont.end()
#define pb push_back
#define fi first
#define se second
#define DEBUG(x) cerr << (#x) << ": " << (x) << '\n'
 
using namespace std;
 
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef long long ll;
typedef unsigned long long ull;
 
template<class T> bool uin(T &a, T b) {return (a < b ? false : (a = b, true));}
template<class T> bool uax(T &a, T b) {return (a > b ? false : (a = b, true));}
 
ifstream f("laser.in");
ofstream g("laser.out");
 
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
#ifdef LOCAL_DEFINE
  freopen(".in", "r", stdin);
#endif

  const double PI = acos(-1);
  const double EPS = 0.00001;

  int n;
  f >> n;
  
  vector<pair<double, double>> segm(n);
  vector<double> points(2 * n);
  
  for (int i = 0; i < n; ++i) {
    auto readAng = [&]() {
      int x, y;
      f >> x >> y;
      double ang = atan2(y, x);
      if (ang < 0) { // le bagam in [0, 360]
        ang += 2 * PI;
      }
      return ang;
    };
    
    double ang1 = readAng();
    double ang2 = readAng();
    
    if (ang1 > ang2) {
      swap(ang1, ang2);
    }
    
    segm[i] = {ang1, ang2};
    points[2 * i] = ang1;
    points[2 * i + 1] = ang2;
  }
  
  sort(points.begin(), points.end());
  
  auto aux = points;
  aux.emplace_back(points[0] + PI);
  for (int i = 0; i < 2 * n; ++i) {
    points[i] = (aux[i] + aux[i + 1]) * 0.5;
    if (points[i] >= 2 * PI) {
      points[i] -= 2 * PI;
    }
    assert(points[i] >= 0);
  }
  
  sort(points.begin(), points.end());
  
  auto intersects = [&](double ang, pair<double, double> segm) {
    if (segm.second - segm.first > PI) {
      return segm.first + EPS >= ang || ang >= segm.second - EPS;
    }
    return segm.first - EPS <= ang && ang <= segm.second + EPS;
  };
  
  vector<bitset<1025>> gauss(n);
  
  for (int i = 0; i < n; ++i) {
    bool state;
    f >> state;
    gauss[i][2 * n] = state;
    for (int j = 0; j < 2 * n; ++j) {
      gauss[i][j] = intersects(points[j], segm[i]);
    }
  }
  
  int i = 0, j = 0;
  while (i < n && j < 2 * n + 1) {
    int k = i;
    while (k < n && !gauss[k][j]) {
      ++k;
    }
    
    if (k == n) {
      ++j;
      continue;
    }
    
    if (i != k) {
      swap(gauss[i], gauss[k]);
    }
    
    for (int row = i + 1; row < n; ++row) {
      if (gauss[row][j]) {
        gauss[row] ^= gauss[i];
      }
    }
    
    ++i;
    ++j;
  }
  
  int res = 0;
  vector<bool> ans(2 * n);
  for (int i = n - 1; i >= 0; --i) {
    for (int j = 0; j < 2 * n; ++j) {
      if (!gauss[i][j]) {
        continue;
      }
      
      ans[j] = gauss[i][2 * n];
      for (int k = j + 1; k < 2 * n; ++k) {
        ans[j] = ans[j] ^ (ans[k] & gauss[i][k]);
      }
      if (ans[j]) {
        ++res;
      }
      break;
    }
  }
  
  g << res << '\n';
  
  g.precision(7);
  g << fixed;
  for (int i = 0; i < 2 * n; ++i) {
    if (ans[i]) {
      g << points[i] * 180.0 / PI << '\n';
    }
  }
  
  f.close();
  g.close();
  

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