Cod sursa(job #1698046)

Utilizator sucureiSucureiRobert sucurei Data 3 mai 2016 15:48:09
Problema Laser Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.1 kb
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>

#define pi 3.141592653
#define x first
#define y second

using namespace std;

ifstream fin("laser.in");
ofstream fout("laser.out");

struct segment {

    double x1, y1;
    double x2, y2;

} segments[520];

int a[520][1050];

int ok[1050], aprins[520];

pair<double, double> vec[1050], p0 = make_pair(0, 0);

double det(pair<double, double> a, pair<double, double> b, pair<double, double> c) {

    return (a.x - c.x)*(b.y - c.y) - (a.y - c.y)*(b.x - c.x);

}

bool cmp(const pair<double, double> &a, const pair<double, double> &b) {

    return (det(a, b, p0) < 0);

}

bool segIntersection(pair<double, double> a, pair<double, double> b, pair<double, double> c, pair<double, double> d) {

    if (1LL * det(a, b, c)*det(a, b, d) < 0 && 1LL * det(c, d, a)*det(c, d, b) < 0)
        return true;

    return false;

}

int main() {

    int n, m = 0;

    fin >> n;

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

        fin >> segments[i].x1 >> segments[i].y1 >> segments[i].x2 >> segments[i].y2;
        vec[++m] = make_pair(segments[i].x1, segments[i].y1);
        vec[++m] = make_pair(segments[i].x2, segments[i].y2);

    }

    for (int i = 1; i <= n; ++i)
        fin >> aprins[i];

    sort(vec + 1, vec + m + 1, cmp);

    vec[m + 1] = vec[1];

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

        vec[i].x = ((vec[i].x + vec[i + 1].x) / 2) * 10005;
        vec[i].y = ((vec[i].y + vec[i + 1].y) / 2) * 10005;

    }

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

        for (int j = 1; j <= m; ++j) {

            if (segIntersection(make_pair(segments[i].x1, segments[i].y1), make_pair(segments[i].x2, segments[i].y2), vec[j], p0))
                a[i][j] = 1;

        }

        a[i][m + 1] = (aprins[i] ? 1 : 0);

    }

    int i = 1, j = 1;

    while (i <= n && j <= m) {

        int k;

        for (k = i; k <= n; ++k)
            if (a[k][j])
                break;

        if (k == n + 1) {

            ++j;
            continue;

        }

        for (int l = 1; l <= m + 1; ++l)
            swap(a[i][l], a[k][l]);

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

            if (a[k][j] == 0)
                continue;

            for (int l = j; l <= m + 1; ++l)
                a[k][l] = (a[k][l] + a[i][l]) % 2;

        }

        ++i, ++j;

    }

    for (int i = n; i; --i) {

        for (int j = 1; j <= m; ++j) {

            if (a[i][j]) {

                ok[j] = a[i][m + 1];

                for (int l = j + 1; l <= m; ++l)
                    ok[j] = (ok[j] + ok[l] * a[i][l]) % 2;

                break;

            }

        }

    }

    int sol = 0;

    for (int i = 1; i <= m; ++i)
        if (ok[i])
            ++sol;

    fout << sol << '\n';

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

        if (!ok[i])
            continue;

        double res = atan2(vec[i].y, vec[i].x) * 180 / pi;

        if (res < 0)
            res += 360;

        fout << setprecision(6) << fixed << res << '\n';

    }

    return 0;
}