Raza ONI VII 2022

/**Aici ai sursa mea de la problema Raza ONI VII 2022 cu explicatii. .
O poti citi si cand ne vedem iti explic daca e ceva ce nu ai inteles.  ~ George   */
#include <fstream>
using namespace std;
ifstream cin("raza.in");
ofstream cout("raza.out");
/**
   Patratul de latura razei ce incepe din coord (xA,yA).
   A             B
    -------------
    |           |
    |           |
    |           |
    |           |
    -------------
   D             C

*/
int Sec[100001];
int main()
{
    int cerinta , n ,s ;
    cin>>cerinta>>n>>s;
    if(cerinta==1)
    {
        int cnt = 0;
        for(int i  = 1;i<=n;i++)
        {
            //cout<<"Roverul "<<i<<":\n";
            int l , c , r;
            bool intersect = false;
            cin>>l>>c>>r;

            /**Verificam daca AB se intersecteaza cu diagonala.
            Diagonala in cazul nostru se afla pe pozitia unde l=c iar c creste cu raza - 1.
            Se intersecteaza daca in poz intitiala e inaintea diagonalei sau pe ea (c<=l).
            Iar pozitia finala a coloanei este mai mare sau egala cu coord liniei.  */

            if(c<=l&&c+r - 1>=l)
            {
                 intersect = true;
                // cout<<"AB\n";
            }

            /**Verificam daca AD se intersecteaza cu diagonala. Linia creste cu raza.
            Se poate intersecta daca in poz intitiala este deasupra diagonalei si coborand
            se intersecteaza cu aceasta. */
            if(l<=c&&l+r - 1>=c)
            {
                intersect = true;
               // cout<<"AD\n";
            }

            /**
                Mai avem de verificat BC si DC.
                DC fiind paralel cu AB verificarea se face similar
                doar ca coordonata liniei incepe de la l+r in loc de l
                iar la BC se face ca la AD dar coordonata coloanei incepe cu c+r.
            */
            int cl = l + r - 1; ///Coordonata liniei.
            int cc = c + r - 1; ///Coordonata coloanei.

            ///DC
            if(c<=cl&&c+r - 1>=cl)
            {
                 intersect = true;
                // cout<<"DC\n";
            }
            ///BC
            if(l<=cc&&l+r - 1>=cc)
            {
                intersect = true;
                //cout<<"BC\n";
            }
            ///Daca s-a intersectat macar odata incrementam contorul.
            if(intersect == true)
                cnt++;
        }
        cout<<cnt;
    }

    if(cerinta==2)
    {
        /**Acum pe langa intersectia cu diagonala , ne intereseaza mai exact
        in a cata secunda are loc aceasta intersectie. Avem urmatoarea problema:
        numaram de mai multe ori aceiasi intersectie cand intersectia are loc pe un
        punct al patratului.
        EX: 3 3 . L = 3 , C = 3 , R = 3. Intersectiile au loc in punctele
        A si C . Pentru ca punctul A face parte si din AB si din AD il vom numara de doua ori.
        La fel se intampla si pentru C,  fiind in BC si DC.

        Solutia e simpla : Mai intai verificam pentru AB inclusiv punctul B daca are loc intersectie acolo.
        Apoi pentru BC verficam secundele de la  R+1 pana la 2*R-1 .  Adica verificam daca linia in intervalul
        l+1 -> l+r-1 se intersecteaza cu diagonala. Similar facem si pentru restul.
        Partea asta poti sa imi ceri sa ti-o explic si vei intelege foarte usor cu un desen.*/

        /**
            Putem avea maxim 2 intersectii. Sa spunem ca stim secundele la care
            au loc respectivele intersectii(-1 daca nu au loc). Ce facem apoi?
            Putem marca pe o scara a timpului secundele in care se intersecteaza.

            Sa consideram un tablou Sec in care marcam cate rovere se intersecteaza in
            acea secunda. Daca Sec[5] = 3 inseamna ca in secunda 5, 3 rovere se intersecteaza
            cu diagonala principala.

            Sa luam raza = 6 si o intersectie in secunda 9.(x = 9).
            Perioada este 4 * raza - 4 = 20.
            Prima intersectie va avea loc in secunda 20*0 + 9.
            A doua intersectie va avea loc in secunda 20*1 + 9.
            A treia intersectie va avea loc in secunda 20*2 + 9.
            Si asa mai departe. Putem marca aceste secunde in stil ciur :

            for(int i = x ; i<=S; i+=perioada)
                Sec[i]++;

            ANALIZA TIMPULUI IN CEL MAI RAU CAZ :
            Cea mai mica perioada este 8 (pentru r = 3) asadar o astfel de marcare
            in cel mai rau caz posibil , unde S = 100k va efectua 100k/8 operatii
            pentru un singur rover cu o singura intersectie (12.5k). Pentru doua intersectii
            vor fi 25k operatii. In restrictii ni se spune ca sunt maxim 1000 rovere care se intersecteaza
            cu diagonala. Asadar in cel mai rau caz putem avea 25k * 1000 (25 mil operatii in care adunam in Sec[i]).
            Am putea sa verificam de fiecare data cand adaugam frecventa daca este cea pe care o cautam dar atunci am
            face 25 mil comparatii asa ca e mai bine sa parcurgem inca odata Sec la final decat sa verificam de fiecare
            data daca secunda este raspunsul pe care il cautam.


            Solutia oficiala propune sa folosim 3 vectori , in care sa pastram pozitia intersectiei 1 , poz intersectiei 2
            si perioada fiecarui rover. Nu este necesar. Daca au loc intersectii marcam , daca nu , nu.
            */
        for(int i = 1;i<=n;i++)
        {
            //cout<<"Rover "<<i<<": \n";
            int l , c , r;
            cin>>l>>c>>r;
            ///Secundele de la fiecare punct.
            int secA = 1 , secB = r , secC = 2*r-1 , secD = 3*r-2;
            int perioada = 4 * r - 4, cl = l+r-1, cc = c+r-1;
            int punct1 = -1 , punct2 = -1;
            ///Avem intersectie in AB
            if(c<=l&&c+r - 1>=l)
                punct1 = secA + (l - c);
            ///Avem intersectie pe BC
            if(l+1<=cc&&l+r-1>=cc)
            {
                if(punct1==-1)
                    punct1 = secB + (cc - l);
                else punct2 = secB + (cc - l);
            }
            ///Avem intersectie pe CD
            if(cc>=cl&&cc-r+1<=cl)
            {
                if(punct1 == -1)
                    punct1 = secC + (cc - cl);
                else punct2 = secC + (cc-cl);
            }
            ///Avem intersectie pe DA
            if(cl-1>=c&&cl-r+2<=c)
            {
                if(punct1 == -1)
                    punct1 = secD + (cl - c);
                else punct2 = secD + (cl - c);
            }
            /**if(punct1!=-1)
                cout<<"Punct 1: "<<punct1<<'\n';
            if(punct2!=-1)
                cout<<"Punct 2: "<<punct2<<'\n'; */

            ///Acum ca avem secundele punctelor marcam pe Sec.
            if(punct1!=-1)
            {
                for(int i = punct1;i<=s;i+=perioada)
                    Sec[i]++;
            }
            if(punct2!=-1)
            {
                for(int i = punct2;i<=s;i+=perioada)
                    Sec[i]++;
            }
        }
        int maxi = -1 , secmin = -1;
        for(int i = 1;i<=s;i++)
        {
            if(Sec[i]>maxi)
                maxi = Sec[i], secmin = i;
        }
        cout<<maxi<<' '<<secmin;
    }
    return 0;
}