Cod sursa(job #2779896)

Utilizator C_DanyConstantin Daniel C_Dany Data 5 octombrie 2021 14:03:23
Problema Rays Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.73 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;

   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::sync_with_stdio(0); cin.tie(0); cout.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 = [](linie A, 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;
}