Cod sursa(job #3188539)

Utilizator victor_gabrielVictor Tene victor_gabriel Data 3 ianuarie 2024 12:24:58
Problema Rays Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

struct interval {
    double l, r;
};

vector<interval> lft;
vector<interval> rgt;

inline bool cmp(interval a, interval b) {
    return a.l < b.l;
}

int calc(vector<interval> &v) {
    int s = 1;
    sort(v.begin(), v.end(), cmp);

    double val = v[0].r;
    for (int i = 1; i < v.size(); i++) {
        double left = v[i].l;
        double right = v[i].r;
        if (left < val)
            val = min(val, right);
        else
            s++, val = right;
    }
    return s;
}

int main() {
    ifstream fin("rays.in");
    ofstream fout("rays.out");

    int n;
    fin >> n;
    for (int i = 1; i <= n; i++) {
        int x, y1, y2;
        fin >> x >> y1 >> y2;
        if (y1 > y2)
            swap(y1, y2);

        double a1 = atan2(y1, abs(x));
        double a2 = atan2(y2, abs(x));
        if (x > 0)
            rgt.push_back({a1, a2});
        else
            lft.push_back({a1, a2});
    }

    int sol = 0;
    if (!lft.empty())
        sol += calc(lft);
    if (!rgt.empty())
        sol += calc(rgt);
    fout << sol;

    fin.close();
    fout.close();
    return 0;
}