Cod sursa(job #3187437)

Utilizator gianiferSpita Alexandru-Mihai gianifer Data 28 decembrie 2023 22:34:21
Problema Rays Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("rays.in");

ofstream fout("rays.out");
struct segment
{
    double sus, jos;
};
vector<segment> dr;

vector<segment> st;
bool compara(segment a, segment b)
{
    return a.jos < b.jos;
}
int n;
int rezolvare(vector<segment> vect)
{
    int sol = 1;
    double calc = vect[0].sus;
    for (int i = 1; i < vect.size(); i++)
    {
        if (vect[i].jos > calc)
        {
            sol++;
            calc = vect[i].sus;
        }
        else
        {
            if (calc > vect[i].sus)
                calc = min(calc, vect[i].sus);
        }
    }
    return sol;
}
int main()
{
    fin >> n;
    int sol = 0;
    for (int i = 1; i <= n; i++)
    {
        double x, y1, y2;
        fin >> x >> y1 >> y2;
        if (y1 > y2)
            swap(y1, y2);
        if (x > 0)
        {
            dr.push_back({(double)y2 / (double)x, (double)y1 / (double)x});
        }
        else
            st.push_back({(double)y2 / (double)(-x), (double)y1 / (double)(-x)});
    }
    sort(dr.begin(), dr.end(), compara);
    sort(st.begin(), st.end(), compara);
    if (!dr.empty())
        sol += rezolvare(dr);

    if (!st.empty())
        sol += rezolvare(st);
        fout<<sol;
}