Cod sursa(job #1572571)

Utilizator vladrochianVlad Rochian vladrochian Data 18 ianuarie 2016 23:24:53
Problema Laser Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.23 kb
#include <algorithm>
#include <bitset>
#include <cmath>
#include <fstream>
#include <iomanip>
#include <vector>

using namespace std;

const int N_MAX = 512;
const double PI = acos(-1);

ifstream fin("laser.in");
ofstream fout("laser.out");

int N;
vector<pair<double, double>> s;
vector<double> p, a;

bitset<N_MAX * 4 + 5> eq[N_MAX + 5];
int col[N_MAX + 5];

vector<double> ans;

double AbsAtan2(int x, int y) {
   double a = atan2(y, x);
   return a + (a < 0.0) * 2 * PI;
}

bool Intersect(const pair<double, double>& segm, double alpha) {
   double x = segm.first;
   double y = segm.second;
   if (x > y)
      swap(x, y);
   if (y - x < PI)
      return alpha >= x && alpha <= y;
   return alpha <= x || alpha >= y;
}

int main() {
   fin >> N;
   for (int i = 0; i < N; ++i) {
      int x1, y1, x2, y2;
      fin >> x1 >> y1 >> x2 >> y2;
      double alpha1 = AbsAtan2(x1, y1);
      double alpha2 = AbsAtan2(x2, y2);
      s.emplace_back(alpha1, alpha2);
      p.push_back(alpha1);
      p.push_back(alpha2);
   }
   sort(p.begin(), p.end());
   p.push_back(p[0] + 2 * PI);

   a.resize(4 * N);
   for (int i = 0; i < 2 * N; ++i) {
      a[2 * i] = p[i];
      a[2 * i + 1] = (p[i] + p[i + 1]) / 2;
   }
   if (a.back() >= 2 * PI) {
      a.insert(a.begin(), a.back() - 2 * PI);
      a.pop_back();
   }

   for (int i = 0; i < N; ++i) {
      int x;
      fin >> x;
      if (x == 1) eq[i].set(4 * N);
   }

   for (int i = 0; i < N; ++i)
      for (int j = 0; j < 4 * N; ++j)
         eq[i][j] = Intersect(s[i], a[j]);

   int r = 0, c = 0;
   while (r < N && c < 4 * N) {
      if (!eq[r][c]) {
         int i = r + 1;
         while (i < N && !eq[i][c])
            ++i;
         if (i == N) {
            ++c;
            continue;
         }
         swap(eq[r], eq[i]);
      }
      if (eq[r][c])
         for (int i = 0; i < N; ++i)
            if (i != r && eq[i][c])
               eq[i] ^= eq[r];
      col[r] = c;
      ++r; ++c;
   }

   for (int i = 0; i < N; ++i)
      if (eq[i][4 * N])
         ans.push_back(a[col[i]] / PI * 180);

   fout << ans.size() << "\n" << setprecision(6) << fixed;
   for (double i : ans)
      fout << i << "\n";
   return 0;
}