Cod sursa(job #1658259)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 21 martie 2016 11:47:00
Problema Rays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.61 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>

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;
    int x;
    int y;
    int ind;
};


inline bool ev_sort(const event &a, const event &b) {
    return 1ll * a.y * b.x < 1ll * a.x * b.y;
}

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

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

    sort(ev.begin(), ev.end(), ev_sort);

    for(const auto e : ev) {
        if(e.type == 0) {
            wait_list.push(e.ind);
        }
        else {
            if(erased[e.ind]) continue;
            while(!wait_list.empty()) {
                erased[wait_list.front()] = true;
                wait_list.pop();
            }
            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;
}