Pagini recente » Cod sursa (job #1984585) | Cod sursa (job #889885) | Cod sursa (job #2390440) | Cod sursa (job #1087121) | Cod sursa (job #1658238)
#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;
}