Cod sursa(job #2483005)

Utilizator LucaSeriSeritan Luca LucaSeri Data 29 octombrie 2019 09:58:55
Problema Laser Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.35 kb
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
    
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,avx,avx2,abm,mmx,tune=native")

using namespace __gnu_pbds;
using namespace std;
     
#define mp make_pair
#define sz(x) (int)((x).size())
#define all(x) (x).begin(),(x).end()
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define eb emplace_back
 
typedef pair< int, int > pii;
typedef pair< long long, long long > pll;
typedef long long ll;
typedef unsigned long long ull;
typedef vector< int > vi;
typedef vector< vi > vvi;
typedef vector< ll > vll;
typedef vector< vll > vvll;
typedef vector< pii > vpii;
typedef vector< vpii > vvpii;
typedef vector< pll > vpll;
typedef long double ld;
typedef vector< ld > vld;
 
const ll MOD = 1e9 + 7;
 
const ull infull = numeric_limits<unsigned long long>::max();
 
void fix(int &x, ll MOD) {
    x = (x % MOD);
    if(x < 0) x += MOD;
    return;
}
 
ll lgput(ll a, ll b, ll MOD) {
    ll ret = 1;
    a %= MOD;
    while(b) {
        if(b&1) ret = ret*a % MOD;
        a = a*a % MOD;
        b >>= 1;
    }
 
    return ret;
}
 
ll inv(ll a, ll MOD) {
    return lgput(a, MOD-2, MOD);
}
 
struct f {
    int a, b;
    f(int _a = 0, int _b = 0) : a(_a) ,b(_b) {}
    ll eval(int x) {
        return 1ll*x*a + b;
    }
};
 
int binarySearch(int x, vi &v) {
    int pos = 0;
    int l = 1, r = sz(v);
    while(l <= r) {
        int m = l + r >> 1;
        if(v[m] <= x) {
            pos = m;
            l = m + 1;
        } else {
            r = m - 1;
        }
    }
 
    return pos;
}
 
using Matrix = vvi;
 
Matrix mult(Matrix a, Matrix b) {
    assert(a[0].size() == b.size());
 
    Matrix ret(a.size(), vector< int >(b[0].size()));
 
    for(int i = 0; i < a.size(); ++i) {
        for(int j = 0; j < b[0].size(); ++j) {
            for(int k = 0; k < a[0].size(); ++k) {
                ret[i][j] += ((1ll*a[i][k]*b[k][j])%MOD);
                if(ret[i][j] >= MOD) ret[i][j] -= MOD;
            }
        }
    }
 
    return ret;
}


const int MAXN = 512;

bitset< 2*MAXN > gauss[2 * MAXN];

const double PI = acos(-1);
const double eps = 1e-6;
pair< double, double > angles[MAXN];
int p[MAXN];
double unghi(int x, int y) {
    double u = atan2(y, x);
    if(u < 0) u += 2*PI;

    return u;
}

bool intersect(double u, pair< double, double > dr) {
    if(dr.second - dr.first > PI) {
        return u < dr.first + eps || u > dr.second - eps; 
    }

    return (u > dr.first - eps && u < dr.second + eps);
}

int main() {
    #ifdef BLAT
        freopen("stdin", "r", stdin);
        freopen("stderr", "w", stderr);
    #else
        FO(laser);  
    #endif
 
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout.precision(12);
    srand(time(NULL));

    int n;
    cin >> n;

    vector< double > lasere;
    vector< double > drepte;

    for(int i = 1; i <= n; ++i) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;

        double a = unghi(x1, y1), b = unghi(x2, y2);
        if(a > b) swap(a, b);

        angles[i] = {a, b};
        drepte.eb(a);
        drepte.eb(b);
    }

    sort(all(drepte));
        
    for(int i = 0; i < drepte.size(); ++i) {
        lasere.eb((drepte[i] + drepte[i+1]) / 2);
    }

    lasere.eb(drepte.back()*drepte.front() / 2 - 2*PI*(drepte.back()*drepte.front() > 4*PI));

    int m = lasere.size();
    for(int i = 1; i <= n; ++i) {
        for(int j = 1; j <= m; ++j) {
            gauss[i][j] = intersect(lasere[j-1], angles[i]);
        }
    }

    for(int i = 1; i <= n; ++i) {
        int x;
        cin >> x;

        gauss[i][m + 1] = x;
    }

    for(int i = 1; i <= n; ++i) {
        int j = 1;
        while(j <= m + 1 && !gauss[i][j]) ++j;

        if(j > m + 1) continue;

        p[i] = j;
        for(int k = 1; k <= n; ++k) {
            if(i != k && gauss[k][p[i]]) gauss[k] ^= gauss[i];
        }
    }

    vector< double > ans;
    for(int i = 1; i <= n; ++i) {
        if(p[i] && gauss[i][m + 1]) {
            ans.eb(lasere[p[i] - 1]);
        }
    }

    cout << ans.size() << '\n';
    for(auto &x : ans) cout << setprecision(6) << fixed <<  x / PI * 180 << '\n';
    return 0;  
}