Pagini recente » Cod sursa (job #2453443) | Cod sursa (job #2607850) | Cod sursa (job #1621970) | Cod sursa (job #1551836) | Cod sursa (job #1658259)
#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;
}