Cod sursa(job #2239253)

Utilizator NOSCOPEPROKENDYMACHEAMACUMVREAU NOSCOPEPROKENDY Data 10 septembrie 2018 13:00:26
Problema Laser Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.03 kb
#include <bits/stdc++.h>
#define eps 1e-10

using namespace std;

int mat[1030][1030];
int n;

struct Punct
{
    Punct* p;
    int x, y;
    double alfa;
    void calcAlfa()
    {
        alfa = atan2(y, x);
        alfa *= 180. / 3.14159265358979323846264338327950288;
        if(alfa < 0)
            alfa += 360;
    }
    bool operator<(const Punct& o) const
    {
        return alfa < o.alfa;
    }
    bool intersect(double beta) const
    {
        double alfaMin = min(alfa, p->alfa);
        double alfaMax = max(alfa, p->alfa);
        if(alfaMax - alfaMin < 180)
            return alfaMin <= beta && beta <= alfaMax;
        return alfaMin >= beta || alfaMax <= beta;
    }
} v[1030], po[1030];
Punct* d[520];
double unghiuri[1030];
int rez[1030];

int main()
{
    freopen("laser.in", "r", stdin);
    freopen("laser.out", "w", stdout);
    scanf("%d", &n);
    const int n2 = n * 2;
    for(int i = 0; i < n; i++)
    {
        scanf("%d%d%d%d", &po[i * 2 + 0].x, &po[i * 2 + 0].y, &po[i * 2 + 1].x, &po[i * 2 + 1].y);
        po[i * 2 + 0].calcAlfa();
        po[i * 2 + 1].calcAlfa();
        po[i * 2 + 0].p = &po[i * 2 + 1];
        po[i * 2 + 1].p = &po[i * 2 + 0];
        d[i] = &po[i * 2 + 0];
        v[i * 2 + 0] = po[i * 2 + 0];
        v[i * 2 + 1] = po[i * 2 + 1];
    }
    for(int i = 0; i < n; i++)
        scanf("%d", &mat[i][n2]);
    sort(v, v + n * 2);
    for(int i = 0; i < n2 - 1; i++)
    {
        double alfa = (v[i].alfa + v[i + 1].alfa) / 2.;
        unghiuri[i] = alfa;
        for(int j = 0; j < n; j++)
        {
            if(d[j]->intersect(alfa))
                mat[j][i] = 1;
            else mat[j][i] = 0;
        }
    }
    double alfa = (360 - v[n2 - 1].alfa - v[0].alfa) / 2.;
    if(alfa < 0)
        alfa += 360;
    unghiuri[n2 - 1] = alfa;
    for(int j = 0; j < n; j++)
    {
        if(d[j]->intersect(alfa))
            mat[j][n2 - 1] = 1;
        else mat[j][n2 - 1] = 0;
    }

    int lc = 0, cc = 0;
    while(lc < n && cc < n2)
    {
        int k = lc;
        while(mat[k][cc] == 0 && k < n) k++;
        if(k == n)
        {
            cc++;
            continue;
        }
        if(k != lc)
            for(int i = cc; i <= n2; i++)
                swap(mat[lc][i], mat[k][i]);
        for(int i = lc + 1; i < n; i++)
        {
            for(int j = cc + 1; j <= n2; j++)
                mat[i][j] ^= mat[i][cc] & mat[lc][j];
            mat[i][cc] = 0;
        }
        lc++; cc++;
    }
    int nrez = 0;
    for(int i = lc - 1; i >= 0; i--)
    {
        int j = 0;
        for(; j < n2 && mat[i][j] == 0; j++);
        if(j != n2)
        {
            int x = j;
            int rest = 0;
            for(j++; j < n2; j++)
                rest ^= mat[i][j] & rez[j];
            rez[x] = rest ^ mat[i][n2];
            if(rez[x] == 1) nrez++;
        }
    }
    printf("%d\n", nrez);
    for(int i = 0; i < n2; i++)
        if(rez[i] == 1)
            printf("%.6f\n", unghiuri[i]);
    return 0;
}