Pagini recente » Cod sursa (job #234230) | Cod sursa (job #498848) | Cod sursa (job #2309642) | Cod sursa (job #2818882) | Cod sursa (job #1658252)
#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;
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);
queue<int> wait_list;
for(int i = 0; i < seg.size(); i++) {
ev.push_back({0, atan2(seg[i].y1, seg[i].x), i});
ev.push_back({1, atan2(seg[i].y2, seg[i].x), 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(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;
}