Zadanko logiczne

Hej!
Mam zadanko:

 Wycinanka
Jaś odgrzebał na strychu stary kawałek wyprawionej skóry dzika. Skóra ma kształt prostokąta, ale posiada
dziury. Jaś postanowił wyciąć z niej kwadrat o maksymalnym polu.
Napisz program, który:
- wczytuje z standardowego wejścia opis skóry i położenie dziur
- znajduje kwadrat o maksymalnym polu niepogryzionym przez mole
- zapisuje wynik na standardowe wyjście.
**Wejście**
W pierwszym wierszu standardowego wejścia zapisano dwie liczby całkowite dodatnie, oddzielone pojedynczym
odstępem: długość skóry D, oraz jej szerokość S (1 < D, S < 50). W drugim wierszu zapisano LD liczbę dziur
(1 < LD < 500), a w kolejnych LD wierszach zapisano po dwie wartości całkowitych, która odpowiadają
położeniu dziur.
Wyjście
W pierwszym wierszu standardowego wyjścia zapisz pole największego kwadratu jaki można wyciąć z danego
kawałka skóry.
**Przykłady**
Wejście:
6 7
1
2 3
Wyjście:
16

Wejście:
10 17
2
5 6
7 8
Wyjście:
81

Wejście:
15 20
3
3 6
9 8
12 15
Wyjście:
121

Samo zrozumienie zadanka: prościzna.
Problem z zapisaniem.
Pomysł: tablica dwuwymiarowa i sprawdzanie po kolei.
Ale czy to nie będzie za długie?
Jakieś inne pomysły?
Albo coś matematycznego, czego nie zauważyłam?

stwórz klase prostokąt trzymającą wszystkie możliwe, największe prostokąty i wybierz ten, którego krótszy bok jest najdłuży ze wszystkich prostokątów

edit

stwórz klase prostokąt i vector trzymający wszystkie możliwe, największe prostokąty i wybierz ten, którego krótszy bok jest najdłuższy ze wszystkich prostokątów

Więc generujemy wszystkie kwadraty (4) od każdego punktu? Spoko, przed chwilą na to wpadłam. Teraz tylko zapis.

ZosiaZamoyska napisał(a):

Więc generujemy wszystkie kwadraty (4) od każdego punktu? Spoko, przed chwilą na to wpadłam. Teraz tylko zapis.

no właśnie to chyba nie wystarczy

może jednak zrobić każdy z każdym + dodać jeszcze punkty na obwodzie prostokąta, wyznaczone ze współrzędnych dziur no i wierzchołki samego prostokąta, to byłyby punkty, potem jak już wyznaczysz wszystkie możliwe prostokąty, eliminujesz te, na które zawierają dziury w sobie i dalej tak jak napisałem wyżej

no tak, tablica par, każde z każdym... A co jak między nimi będzie dziura? może posortować? Ale co wtedy?

prostokąt możesz zapisać w postaci 2 punktów

http://i.imgur.com/sBkdOkF.png

zapisujesz wszystkie możliwe na podstawie zaznaczonych punktów,

potem iterujesz po nich i sprawdzasz czy nie zawierają w sobie(nie na obwodzie) tych punktów

potem wybierasz ten z najdłuzszym krótkim bokiem

Pomysł z tworzeniem wszystkich prostokątów jest najbardziej oczywisty, ale to jest O(n²) i wątpię żeby to był oczekiwany algorytm, bo byłoby to zbyt proste ;)

Było podobne zadanie na OIG rok temu (wystarczy sobie zmapować to do tablicy 2d, w której są dwie wartości - skóra, dziura. Wtedy zadanie sprowadza się do tego samego). Gdzieś mam dobre rozwiązanie do niego, ale nie mogę go teraz znaleźć.
Znalazłem jednak omówienie do tego zadania. Myślę, że wystarczy.

weźcie pod uwage taki przykład http://i.imgur.com/OI1tKsp.png

jak łatwo i szybko wyznaczyć największy prostokąt (ten wewnątrz) ? chyba tylko bruteforce, ale mogę się mylić

dlatego przedstawiłem takie rozwiązanie

Widzę tylko O(n^2) czyli nieco lepiej niż brutal force.

Wydaje mi się, że to jest dokładnie to:
http://www.sciencedirect.com/science/article/pii/0166218X84901240 (Download PDF w lewym górnym rogu)

Ich rozwiązanie ma pesymistyczną złożoność O(n²)

EDIT:
Patrząc na wejście twojego zadania, to masz prostokąt o max szerokości i wysokości 50x50 i max 500 dziur. O(n³) z niską stałą powinien przejść jeśli limit czasowy jest koło 10s.

Rozwiązałam zadanie.
Po prostu całą tablicę wypełniamy 1, a dziury zaznaczamy 0.
I bierzemy najmniejszą wartość, znajdującą się obok (góra, dół, prawo, lewo) i dodajemy 1.
Bierzemy maxymalną wartość, i wypisujemy kwadrat.

 #include <iostream>
using namespace std;
int tab[55][55];
int main()
{
    int a, b, s, d, x, max=0;
    cin>>a>>b;
    for (int i=1; i<=a; i++)
    {
        for (int j=1; j<=b; j++)
        {
            tab[i][j]=1;
        }
    }
    cin>>x;
    for (int i=1; i<=x; i++)
    {
        cin>>s>>d;
        tab[s][d]=0;
    }
    for(int i=1; i<=a; i++)
    {
        for(int j=1; j<=b; j++)
        {
            if(tab[i][j]!=0)
            {
                int min=55;
                if(tab[i-1][j]<tab[i][j-1])
                {
                    if(tab[i-1][j]<tab[i-1][j-1])
                        min=tab[i-1][j];
                    else
                        min=tab[i-1][j-1];
                }
                else
                {
                    if(tab[i][j-1]<tab[i-1][j-1])
                        min=tab[i][j-1];
                    else
                        min=tab[i-1][j-1];
                }
                tab[i][j]=min+1;
                if(tab[i][j]>max)
                    max=tab[i][j];
            }
        }
    }    cout<<max*max<<endl;
}                

To ten kwadrat jednak nie mógł być obrócony?

To znaczy? Jak obrócony?

czerwony punkt = dziura