15154. Cięcia [AL_07_05]

Zadanie:
https://pl.spoj.com/problems/AL_07_05

Skrócony opis problemu:

Mając dany prostokąt w układzie współrzędnym, a także proste pionowe i poziome przecinające ten prostokąt, wypisz pole największego kawałka tego prostokąta przeciętego przez te proste oraz ilość tych największych kawałków. Jest $n$ prostych - pionowe opisane są liczbami naturalnymi, a poziome całkowitymi ujemnymi.

Rozwiązanie:

Najpierw segregujemy liczby wrzucając dodatnie do jednej tablicy i wartości bezwzględne ujemnych do drugiej, i dodajemy do obu tablic wartości skrajne, czyli dla rzędnych 0 i $h$ (gdzie $h$ to wysokość prostokąta), a dla odciętych 0 i $w$ (gdzie $w$ to długość prostokąta). Następnie sortujemy obie tablice rosnąco. Na koniec wyszukujemy maxy różnic między kolejnymi komórkami tablicy dla każdej z nich. Jeśli pojawi się liczba większa od max, którego mamy w danym momencie, to ustawiamy $count=1$, a jeśli jakaś liczba będzie równa max, to robimy $++count$ (w $count$ znajdować się będzie ilość maxów).

Wypisujemy $max \cdot max2$, bo jest to pole największej wysokości z największą szerokością oraz $count \cdot count2$, jako że chcemy uwzględnić każdą wysokość z każdą szerokością.

Złożoność: $O(n \log n)$.

Ostateczny algorytm:

int main()
{
    int tab[100009], tab2[100009]; // tablice z prostymi (odpowiednio pionowymi i poziomymi)
    int h, w, n, x, size = 0, size2 = 0, count, count2, max, max2;
    
    get(h, w, n);
    while(n--)
    {
        get(x);
        if(x > 0)
            tab[size++] = x;
        else
            tab2[size2++] = -x;
    }
    tab[i++] = tab2[j++] = 0;
    tab[i++] = w; tab2[j++] = h;
    sort(tab, tab+size); sort(tab2, tab2+size2);
    for(i = 0, max = -1; i < size-1; ++i) // różnic jest size-1, bo tyle jest par sąsiadujących ze sobą liczb
        if(tab[i+1]-tab[i] > max)
            max = tab[i+1]-tab[i],
            count = 1;
        else if(tab[i+1]-tab[i] == max)
            ++count;
    for(i = 0, max2 = -1; i < size2-1; ++i)
        if(tab2[i+1]-tab2[i] > max2)
            max2 = tab2[i+1]-tab2[i],
            count2 = 1;
        else if(tab2[i+1]-tab2[i] == max2)
            ++count2;
    printf("%lld %u", (long long)max*max2, (unsigned)count*count2); // 1e9*1e9 przekracza inta, 5e4*5e4 mieści się w unsigned int
}