Cod sursa(job #1792072)

Utilizator ade_tomiEnache Adelina ade_tomi Data 29 octombrie 2016 23:36:15
Problema Laser Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.61 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <iomanip>
#include <algorithm>
#include <bitset>
#include <cmath>
using namespace std;

const double PI = acos(-1);

double aatan2 (int x, int y)
{
    double p = atan2(x,y);
    if (p < 0)
        p += 2 * PI;
    return p;
}
double inter (pair <double, double> per , double x)
{
    if (per.second - per.first < PI)
        return (x >= per.first && x <= per.second);
    return (x <= per.first || x >= per.second);

}
vector <double> ats, cmp, sol;
vector <pair <double,double> > pi;
bitset < 512 * 2 + 2 > b[514];
int n, m, col[512];
int main ()
{
    ifstream cin ("laser.in");
    ofstream cout ("laser.out");
    cin >> n;
    int x1, y1, x2, y2;
    for (int i = 1; i <= n; i++)
    {
        cin >> x1 >> y1 >> x2 >> y2;
        double at1 = aatan2(x1, y1);
        double at2 = aatan2(x2, y2);
        if (at1 > at2)
            swap (at1, at2);
        pi.push_back (make_pair(at1, at2));
        ats.push_back(at1);
        ats.push_back(at2);
    }
    sort (ats.begin (), ats.end());
    ats.push_back(ats[0] + 2 * PI);
    for (int i = 0 ; i < 2 * n; i++)
        cmp.push_back ((ats[i] + ats[i + 1]) * 0.5);
    if (cmp.back() >= 2 * PI)
    {
        cmp.insert (cmp.begin(), cmp.back() - 2 * PI);
        cmp.pop_back();
    }
    int x;
    for (int i = 0; i < n; i++)
    {
        cin >> x;
        b[i][2 * n] = x;
    }
    for (int i = 0; i < n; i++)
    {
        for(int j = 0; j < cmp.size(); j++)
            b[i][j] = inter(pi[i], cmp[j]);
    }
 /*   for (int i = 0; i < n * 2 ;i++)
    {
        cout <<setprecision (3) <<  cmp[i] / PI * 180 << " " ;
    }*/
 /*   for (int i = 0; i < n; i++){
        for (int j = 0; j < 2 * n + 1; j++)
            cout << b[i][j] << " " ;
        cout << "\n";
    }
*/
    int l = 0, c = 0;
    while (l < n && c < 2 * n)
    {
        if (b[l][c] == 0)
        {
           
            for (int i = l + 1; i < n; i++)
                if (b[i][c]){
           //         break;
                    swap (b[i], b[l]);
                    break;
                }
             c++;
             continue;
        }
        if (b[l][c])
        for (int i = 0 ; i < n; i++)
            if (i != l && b[i][c] == 1)
                b[i] ^= b[l];
        col[l] = c;
        l ++;
        c ++;
    }
    for (int i = 0; i < n; i++)
        if (b[i][2 * n] == 1)
            sol.push_back (cmp[col[i]] / PI * 180);
        //   sol.push_back(col[i]);
   cout << sol.size() << "\n";
   sort(sol.begin(), sol.end());
   cout << setprecision (6) << fixed;
   for (int i = 0; i < sol.size(); i++)
       cout << sol[i] << "\n";
   return 0;

}