Cod sursa(job #2735783)

Utilizator Cosmin2004_InfoMoldoveanu Cosmin Cosmin2004_Info Data 2 aprilie 2021 20:04:46
Problema Laser Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.75 kb
#include <bits/stdc++.h>

using namespace std;
#define fi first
#define se second
ifstream fin("laser.in");
ofstream fout("laser.out");
using ld = long double;
const int NMAX = 1 << 11;
const ld pi = 2.0 * acos(0.0), eps = 1e-10;
bool A[NMAX][NMAX];
int n, m;
void gauss(vector <bool>& sol) {
    int row, col, x;
    vector <int> where(m, -1);
    for(row = col = 0; row < n && col < m; col++) {
        for(x = row; x < n; x++)
            if(A[x][col])
                break;
        if(x == n) continue;
        for(int i = 0; i <= m; i++) swap(A[row][i], A[x][i]);
        where[col] = row;
        for(int i = 0; i < n; i++) if(i != row) if(A[i][col])
            for(int j = col; j <= m; j++)
                A[i][j] ^= A[row][j];
        row++;
    }
    for(int i = 0; i < m; i++)
        if(where[i] != -1)
            sol[i] = A[where[i]][m];
}
int x, y, x2, y2;
map <ld, bool> angles;
ld getangle(int x, int y) {
    ld a = (ld)atan2(y, x);
    if(a < 0) a = 2 * pi + a;
    return a * 180 / pi;
}
struct P {ld x, y;};
typedef pair <P, P> segm;
segm v[1 << 10];
ld mid(ld a, ld b) {return a > b ? (a + b - 360) / 2 >= 0 ? (a + b - 360) / 2 : 360 + (a + b - 360) / 2 : (a + b) / 2;}
inline bool cmp(ld a, ld b) {return a - b < eps;}
P operator -(P a, P b) {return {a.x - b.x, a.y - b.y};}
int crossproduct(P a, P b) {return a.x * b.y - b.x * a.y;}
inline bool intersect(ld angle, segm s) {
    ld rad = angle * pi / 180.0;
    P r = {cos(rad), sin(rad)};
    ld t = (ld)crossproduct(s.fi, s.se - s.fi) / crossproduct(r, s.se - s.fi);
    ld u = (ld)crossproduct(P{0, 0} - s.fi, r) / crossproduct(s.se - s.fi, r);
    return 0 <= t && 0 <= u && u <= 1;
}

int main()
{
    fout << fixed << setprecision(6);
    fin >> n;
    for(int i = 0; i < n; i++) {
        fin >> x >> y >> x2 >> y2;
        v[i] = {{x, y}, {x2, y2}};
        angles[getangle(x, y)] = true;
        angles[getangle(x2, y2)] = true;
    }
    m = angles.size();
    vector <ld> ang;
    for(auto it = angles.begin(); it != angles.end(); it++) {
        auto j = it; j++; if(j == angles.end()) j = angles.begin();
        ang.push_back(mid(it -> fi, j -> fi));
        //fout << *ang.rbegin() << " ";
    }
    //fout << "\n";
    for(int i = 0; i < m; i++)
        for(int j = 0; j < n; j++)
            A[j][i] = intersect(ang[i], v[j]);
    for(int i = 0; i < n; i++)
        fin >> A[i][m];
    /*for(int i = 0; i < n; i++)
        for(int j = 0; j <= m; j++)
            fout << A[i][j] << " \n"[j == m];*/
    vector <bool> sol(m, 0);
    gauss(sol);
    int cnt = 0;
    for(int i = 0; i < m; i++) cnt += sol[i];
    fout << cnt << "\n";
    for(int i = 0; i < m; i++)
        if(sol[i])
            fout << ang[i] << " ";
    return 0;
}