Cod sursa(job #2779439)

Utilizator bubblegumixUdrea Robert bubblegumix Data 3 octombrie 2021 19:18:40
Problema Rays Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.74 kb
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
using namespace std;
ifstream INPUT("rays.in");
ofstream OUTPUT("rays.out");

struct linie
{
    double up;
    double down;
};

int                N;
int                Nr1;
int                Nr;
double             X;
double             Y1;
double             Y2;
vector<linie>      LeftLines;
vector<linie>      RightLines;

inline void pewpew(int& Nr, vector<linie>& Lines)
{
    linie Last = *begin(Lines);
    Nr++;
    for (auto itr = begin(Lines) + 1; itr != end(Lines); itr++)
        if ((*itr).up >= Last.down)
            Last.down = max(Last.down, (*itr).down);
        else
        {
            Nr++;
            Last = *itr;
        }
}

int main()
{
    ios_base::sync_with_stdio(false);
    INPUT.tie(0);
    OUTPUT.tie(0);
    INPUT >> N;
    while (N--)
    {
        INPUT >> X >> Y1 >> Y2;
        if (X == 0)
        {
            if (Y1 > 0 && Y2 > 0)
                Nr1 = 1;
            else if (Y1 < 0 && Y2 < 0)
                Nr = 1;
        }
        else
        {
            if (Y1 > Y2)
                swap(Y1, Y2);
            if (X < 0)
                LeftLines.push_back({ -1 * Y2 / X, -1 * Y1 / X });
            else
                RightLines.push_back({ Y2 / X, Y1 / X });
        }
    }

    auto comp = [](const linie& A, const linie& B)->bool { return (A.up == B.up) ? (A.down > B.down) : (A.up > B.up); };
    sort(begin(LeftLines), end(LeftLines), comp);
    sort(begin(RightLines), end(RightLines), comp);

    if (LeftLines.size())
        pewpew(Nr, LeftLines);
    if (RightLines.size())
        pewpew(Nr, RightLines);

    OUTPUT << max(Nr + Nr1, 1);

    return 0;
}