Cod sursa(job #1741916)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 15 august 2016 14:17:21
Problema Laser Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.09 kb
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;

ifstream cin("laser.in");
ofstream cout("laser.out");

const int MAXN = 512;
const double PI = acos(-1);

struct Segment{
    double x1, y1;
    double x2, y2;
};
Segment v[1 + MAXN];

pair<double, double> ray[1 + 2 * MAXN];
int state[1 + MAXN];
int a[1 + MAXN][1 + 2 * MAXN + 1], value[1 + 2 * MAXN];

double Determinant(pair<double, double> a, pair<double, double> b, pair<double, double> c) {
    return (a.first - c.first) * (b.second - c.second) - (a.second - c.second) * (b.first - c.first);
}

bool Compare(const pair<double, double> &a, const pair<double, double> &b) {
    return (Determinant(a, b, make_pair(0.0, 0.0)) < 0);
}

bool Intersect(pair<double, double> a, pair<double, double> b, pair<double, double> c, pair<double, double> d) {
    if (1LL * Determinant(a, b, c) * Determinant(a, b, d) < 0 && 1LL * Determinant(c, d, a) * Determinant(c, d, b) < 0)
        return true;
    return false;
}

int main() {
    int n, m = 0;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> v[i].x1 >> v[i].y1 >> v[i].x2 >> v[i].y2;
        m++;
        ray[m] = make_pair(v[i].x1, v[i].y1);
        m++;
        ray[m] = make_pair(v[i].x2, v[i].y2);
    }
    for (int i = 1; i <= n; i++)
        cin >> state[i];
    sort(ray + 1, ray + m + 1, Compare);
    ray[m + 1] = ray[1];
    for (int i = 1; i <= m; i++) {
        ray[i].first = ((ray[i].first + ray[i + 1].first) / 2) * 10005;
        ray[i].second = ((ray[i].second + ray[i + 1].second) / 2) * 10005;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++)
            if (Intersect(make_pair(v[i].x1, v[i].y1), make_pair(v[i].x2, v[i].y2), ray[j], make_pair(0.0, 0.0)))
                a[i][j] = 1;
        a[i][m + 1] = state[i];
    }
    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 >= 1; i--)
        for (int j = 1; j <= m; j++)
            if (a[i][j]) {
                value[j] = a[i][m + 1];
                for (int k = j + 1; k <= m; k++)
                    value[j] = (value[j] + value[k] * a[i][k]) % 2;
                break;
            }
    int answer = 0;
    for (int i = 1; i <= m; i++)
        if (value[i])
            answer++;
    cout << answer << "\n";
    for (int i = 1; i <= m; i++)
        if (value[i]) {
            double angle = atan2(ray[i].second, ray[i].first) * 180 / PI;
            if (angle < 0)
                angle += 360;
            cout << fixed << setprecision(6) << angle << "\n";
        }
    return 0;
}