Cod sursa(job #3210138)

Utilizator not_anduAndu Scheusan not_andu Data 5 martie 2024 11:15:17
Problema Laser Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.32 kb
#include <bits/stdc++.h>

using namespace std;

#define INFILE "laser.in"
#define OUTFILE "laser.out"

typedef long double ld;

const int N_MAX = 520;
const ld EPS = 1e-5;

short n;
int coresponder[N_MAX];
vector<ld> angles, bisectors;
pair<ld, ld> segments[N_MAX];
bitset<2 * N_MAX> equation[2 * N_MAX];

ld getAngle(int x, int y){
    ld ans = atan2(y, x) * 180 / M_PI;
    if(ans < 0) ans += 360;
    return ans;
}

bool intersects(ld left, ld right, ld angle){
    if(right - left > 180) return (angle < left + EPS || angle > right - EPS);
    return (left < angle + EPS && angle - EPS < right);
}

void solve(){

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

        int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;

        ld angle1 = getAngle(x1, y1);
        ld angle2 = getAngle(x2, y2);
        if(angle1 > angle2) swap(angle1, angle2);

        segments[i] = make_pair(angle1, angle2);
        angles.push_back(angle1), angles.push_back(angle2);

    }

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

    int m = angles.size();

    for(int i = 0; i < m - 1; ++i){
        bisectors.push_back((angles[i] + angles[i + 1]) / 2.0);
    }

    bisectors.push_back((angles[m - 1] + angles[0] + 360) / 2.0);
    if(bisectors[bisectors.size() - 1] > 360){
        bisectors[bisectors.size() - 1] -= 360;
    }

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

        for(int j = 1; j <= m; ++j){
            equation[i][j] = intersects(segments[i].first, segments[i].second, bisectors[j - 1]);
        }

        short state; cin >> state;
        equation[i][m + 1] = state;

    }

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

        int j = 1;
        for(; j <= m + 1; ++j){
            if(equation[i][j] != 0) break;
        }

        if(j == m + 2) continue;

        coresponder[i] = j;

        for(j = 1; j <= n; ++j){
            if(i != j && equation[j][coresponder[i]] != 0) equation[j] ^= equation[i];
        }

    }

    vector<ld> ans;
    for(int i = 1; i <= n; ++i){
        if(coresponder[i] != 0 && equation[i][m + 1] != 0) ans.push_back(bisectors[coresponder[i] - 1]) ;
    }

    cout << ans.size() << '\n';
    for(auto &it : ans){
        cout << fixed << setprecision(6) << it << '\n';
    }

}

int main(){
    ios_base::sync_with_stdio(false);
    freopen(INFILE, "r", stdin);
    freopen(OUTFILE, "w", stdout);
    cin.tie(0), cout.tie(0);
    solve();
    return 0;
}