Cod sursa(job #2638445)

Utilizator segtreapMihnea Andreescu segtreap Data 28 iulie 2020 12:06:47
Problema Laser Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.7 kb
#include <bits/stdc++.h>

using namespace std;

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

int X1, Y1, X2, Y2, i, n, j, p[666], xr, m;
bitset<666> a[666];
ld angle1, angle2;
pair<ld, ld> A[666];
vector<ld> ans, v, bisect;

ld get_angle(int x, int y) {
  ld angle = atan2(y,x);
  if(angle < 0)
    angle += 2*PI;
  return angle;
}

bool intersect(ld x, ld y, ld z) {
  if(y-x > PI)
    return (z<x+EPS || z>y-EPS);
  return (x<z+EPS && z-EPS<y);
}

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

  cin >> n;

  for(i=1; i<=n; ++i) {
    cin >> X1 >> Y1 >> X2 >> Y2;

    angle1 = get_angle(X1, Y1);
    angle2 = get_angle(X2, Y2);
    if(angle1 > angle2)
      swap(angle1, angle2);
    A[i] = {angle1, angle2};
    v.push_back(angle1);
    v.push_back(angle2);
  }

  sort(v.begin(), v.end());

  m = v.size();
  for(i=0; i<m-1; ++i)
    bisect.push_back( (v[i]+v[i+1])/2 );

  bisect.push_back( ( v[0]+2*PI + v[m-1] )/2 );
  if(bisect.back() > 2*PI)
    bisect.back() -= 2*PI;

  for(i=1; i<=n; ++i) {
    for(j=1; j<=m; ++j)
      a[i][j] = intersect(A[i].first, A[i].second, bisect[j-1]);
    scanf("%d", &xr);
    a[i][m+1] = xr;
  }

  for(i=1; i<=n; ++i) {
    for(j=1; j<=m+1; ++j)
      if(a[i][j])
        break;

    if(j==m+2)
      continue;
    p[i] = j;

    for(j=1; j<=n; ++j)
      if(i!=j && a[j][p[i]])
        a[j] ^= a[i];
  }

  for(i=1; i<=n; ++i)
    if(p[i] && a[i][m+1])
      ans.push_back(bisect[p[i]-1]);

  cout << (int) ans.size() << "\n";
  for(auto x : ans) {
    cout << fixed << setprecision(6) << x / PI * 180 << "\n";
  }

  return 0;
}