Cod sursa(job #1363724)

Utilizator retrogradLucian Bicsi retrograd Data 27 februarie 2015 10:33:55
Problema Laser Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.49 kb
#include<fstream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<unordered_map>

using namespace std;
typedef double var;

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

#define eps 1e-7
#define PI 3.14159265359

unordered_map<var, bool> H;

struct Interval {
    var p1, p2;
    bool stare;
    Interval(var a, var b) {
        p1 = a;
        p2 = b;
    }
};

vector<Interval> INTERVALE;
vector<var> SOL;

var round(var val) {
    return double((int64_t)(val*1e7))*1e-7;
}


bool inint(var val, var c1, var c2) {
    if(c1 <= val && c2 >= val) return true;
    if(c1 <= val+360 && c2 >= val+360) return true;
    if(c1 <= val-360 && c2 >= val-360) return true;

    return false;
}

int main() {
    int n;
    int x1, x2, y1, y2;
    fin>>n;
    for(int i=1; i<=n; i++) {
        fin>>x1>>y1>>x2>>y2;
        var p1 = 1.0*y1/x1, p2 = 1.0*y2/x2;



        p1 = atan(p1)/PI;
        if(x1<0&&y1>0) p1++;
        else if(x1<0&&y1<0)p1++;
        else if(x1>0&&y1<0)p1+=2;

        p2 = atan(p2)/PI;
        if(x2<0&&y2>0) p2++;
        else if(x2<0&&y2<0)p2++;
        else if(x2>0&&y2<0)p2+=2;


        if(p1 > p2) {
            swap(p1, p2);
        }
        if(p2-p1 > 1) {
            p1+=2;
            swap(p1, p2);
        }
        p1 *= 180;
        p2 *= 180;

        INTERVALE.push_back(Interval(p1, p2));
    }

    for(int i=0; i<n; i++) {
        bool s;
        fin>>s;
        INTERVALE[i].stare = s;
    }

    sort(INTERVALE.begin(), INTERVALE.end(), [](Interval a, Interval b) {
         return a.p2 < b.p2;
         });



    bool gata = 0;
    while(!gata) {
        gata = 1;
        for(var i=n-1; i>=0; i--) {
            Interval &in = INTERVALE[i];
            if(!in.stare) {
                continue;
            }
            var val = in.p2 - eps;
            val = round(val);
            if(H[val]) {
                H.erase(val);
            } else {
                H[val] = 1;
            }
            gata = 0;
            for(var j=n-1; j>=0; j--) {
                Interval &inp = INTERVALE[j];
                if(inint(val, inp.p1, inp.p2)) {
                    inp.stare ^= 1;
                }
            }
            in.stare = 0;
        }
    }

    fout<<H.size()<<'\n';
    for(auto &h : H) {
        var sol = h.first;
        if(sol > 360) sol -= 360;
        fout<<fixed<<setprecision(8)<<sol<<'\n';
    }

    return 0;
}