Cod sursa(job #1658238)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 21 martie 2016 11:32:33
Problema Rays Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.89 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

ifstream in("rays.in");
ofstream out("rays.out");

const double eps = 1e-7;

struct segment {
    int x;
    int y1;
    int y2;
};

struct event {
    int type;
    double time;
    int ind;
};

inline int comp(const double &a, const double &b) {
    if(a - b < -eps) return -1;
    if(a - b > eps) return 1;
    return 0;
}

inline bool ev_sort(const event &a, const event &b) {
    if(comp(a.time, b.time) == 0) return a.type < b.type;
    return comp(a.time, b.time) < 0;
}

int solve(const vector<segment> &seg) {
    int cnt = 0;
    vector<event> ev;
    vector<bool> erased(seg.size(), false);
    vector<int> wait_list;

    for(int i = 0; i < seg.size(); i++) {
        ev.push_back({0, atan(seg[i].y1), i});
        ev.push_back({1, atan(seg[i].y2), i});
    }

    sort(ev.begin(), ev.end(), ev_sort);
    /*for(const auto e : ev) {
        out << e.time << ' ' << e.type << ' ' << e.ind << '\n';
    }
    out << "----------\n";*/

    for(const auto e : ev) {
        if(e.type == 0) {
            wait_list.push_back(e.ind);
        }
        else {
            if(erased[e.ind]) continue;
            for(const auto ind : wait_list) {
                erased[ind] = true;
            }
            wait_list.clear();
            cnt++;
        }
    }

    return cnt;
}

int main() {
    int n;

    in >> n;

    vector<segment> leftSeg;
    vector<segment> rightSeg;

    for(int i = 0, x, y1, y2; i < n; i++) {
        in >> x >> y1 >> y2;
        int _y1 = min(y1, y2);
        int _y2 = max(y1, y2);
        if(x < 0) leftSeg.push_back({x, _y1, _y2});
        else rightSeg.push_back({x, _y1, _y2});
    }

    int ans = 0;

    ans += solve(rightSeg);
    ans += solve(leftSeg);

    out << ans << '\n';
    return 0;
}