Cod sursa(job #1450414)

Utilizator smaraldaSmaranda Dinu smaralda Data 13 iunie 2015 12:00:52
Problema Laser Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.16 kb
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<math.h>
using namespace std;

const double pi = 3.14159265359;
const int NMAX = 520;

struct SEGMENT {
    pair <int, int> end1, end2;

    void read() {
        scanf("%d%d%d%d", &end1.first, &end1.second, &end2.first, &end2.second);
    }
};
SEGMENT seg[NMAX];
vector < pair <int, int> > pts;
pair <double, double> mid[NMAX * 2];
vector <double> angle;
int n;

bool iau[2 * NMAX], coef[NMAX][2 * NMAX];

bool cmp (pair <int, int> a, pair <int, int> b) {
    return atan2(a.second, a.first) < atan2(b.second, b.first);
}

int ccw (pair <double, double> P1, pair <double, double> P2, pair <double, double> P3) {
    double cp = (P2.first - P1.first) * (P3.second - P2.second) - 
                (P2.second - P1.second) * (P3.first - P2.first);
    if(cp <= 0) return -1;
    return 1;
}

bool intersect (SEGMENT s, pair <double, double> p) {
    pair <double, double> A, B, C, D;

    A = s.end1;
    B = s.end2;
    C = make_pair(0, 0);
    D = p;

    return ccw(A, B, C) * ccw(A, B, D) <= 0 && ccw(C, D, A) * ccw(C, D, B) <= 0;
}

void swapLines (int a, int b) {
    for(int i = 1; i <= n; ++ i)
        swap(coef[a][i], coef[b][i]);
}

int main() {
    freopen("laser.in", "r", stdin);
    freopen("laser.out", "w", stdout);
    int k, flag, m, i, j, line;

    scanf("%d", &n);
    for(i = 1; i <= n; ++ i) {
        seg[i].read();
        pts.push_back(seg[i].end1);
        pts.push_back(seg[i].end2);
    }

    sort(pts.begin(), pts.end(), cmp);
    pts.push_back(pts[0]);

    m = 0;
    for(i = 0; i < pts.size() - 1; ++ i) {
        ++ m;

        mid[m].first = (pts[i].first + pts[i + 1].first) * 0.5;
        mid[m].second = (pts[i].second + pts[i + 1].second) * 0.5;
    }

    for(i = 1; i <= n; ++ i)
        for(j = 1; j <= m; ++ j)
            if(intersect(seg[i], mid[j])) 
                coef[i][j] = 1;
            //    fprintf(stderr, "%d %d %d %d -> %lf %lf\n", seg[i].end1.first, seg[i].end1.second, seg[i].end2.first, seg[i].end2.second, mid[j].first, mid[j].second);
    for(i = 1; i <= n; ++ i)
        scanf("%d", &coef[i][m + 1]);

    for(j = 1; j <= m + 1; ++ j) {
        flag = 0;
        for(i = j; i <= n; ++ i) 
            if(coef[i][j]) {
                swapLines(j, i);
                line = i;
                flag = 1;
                break;
            }
        if(!flag)
            continue;
        
        for(i = j + 1; i <= n; ++ i)
            if(coef[i][j])
                for(k = j; k <= m + 1; ++ k)
                    coef[i][k] ^= coef[line][k];
    }

    for(i = 1; i <= n; ++ i) {
        flag = 0;
        for(j = 1; j <= m; ++ j)
            if(coef[i][j]) {
                flag = 1;
                break;
            }
        if(!flag)
            continue;

        iau[j] = coef[i][m + 1];
        for(k = j + 1; k <= m; ++ k)
            iau[j] ^= iau[k] * coef[i][k];
    }

    for(i = 1; i <= m; ++ i)
        if(iau[i]) 
            angle.push_back(atan2(mid[i].second, mid[i].first) * 180 / pi);
    
    printf("%d\n", angle.size());
    for(i = 0; i < angle.size(); ++ i) {
        if(angle[i] < 0)
            angle[i] += 360;
        printf("%lf\n", angle[i]);
    }
    return 0;
}