Cod sursa(job #1451926)

Utilizator smaraldaSmaranda Dinu smaralda Data 19 iunie 2015 00:04:55
Problema Laser Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.09 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);
        end1.first *= 2;
        end1.second *= 2;
        end2.first *= 2;
        end2.second *= 2;
    }
};
SEGMENT seg[NMAX];
vector < pair <int, int> > pts;
pair <double, double> mid[NMAX * 2];
vector <double> angle;
int n, m;

int 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 <int, int> P1, pair <int, int> P2, pair <int, int> 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;
}

void getCoef (int &a, int &b, int &c, pair<int, int> P1, pair <int, int> P2) {
    int x1 = P1.first, x2 = P2.first, y1 = P1.second, y2 = P2.second;

    a = y1 - y2;
    b = x2- x1;
    c = x1 * y2 - x2 * y1;
}

bool intersect (SEGMENT s, pair <int, int> p) {
    pair <int, int> A, B, C, D;
    int a1, a2, b1, b2, c1, c2;
    double x, y;

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

    getCoef(a1, b1, c1, A, B);
    getCoef(a2, b2, c2, C, D);
    
    if(a1 * b2 - a2 * b1 == 0) return 0;
    x = ((double)c2 * b1 - c1 * b2) / ((double)a1 * b2 - a2 * b1);
    y = ((double)- c1 - a1 * x) / (double)b1;

    bool ans = x <= max(A.first, B.first) && x >= min(A.first, B.first) && 
           y <= max(A.second, B.second) && y >= min(A.second, B.second);

//    fprintf(stderr, "%d %d %d %d, pt = %d %d, x = %lf, y = %lf - %d\n", s.end1.first, s.end1.second, s.end2.first, s.end2.second, p.first, p.second, x, y, ans);
    return ans;
}

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

void printec() {
    for(int i = 1; i <= n; ++ i) {
        for(int k = 1; k <= m; ++ k)
            fprintf(stderr, "%d ", coef[i][k]);
        fprintf(stderr, "= %d\n", coef[i][m + 1]);
    }
    fprintf(stderr, "\n");
}

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

    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]);


    line = 1;
    for(j = 1; j <= m; ++ j) {
        for(i = line; i <= n; ++ i) 
            if(coef[i][j]) 
                break;
        if(i == n + 1)
            continue;
   //     fprintf(stderr, "*j = %d, line = %d\n", j, i);
     //   printec();
       // swapLines(last, i);

        for(i = 1; i <= n; ++ i)
            if(i != line && coef[i][j])
                for(k = 1; k <= m + 1; ++ k)
                    coef[i][k] ^= coef[line][k];
        ++ line;
      //  printec();
    }

 //   printec();

    
    for(i = line; i >= 1; -- i) 
        for(j = 1; j <= m; ++ j)
            if(coef[i][j]) {
                iau[j] = coef[i][m + 1];
                break;
            }
    

    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;
}