Zapytania

05.01.2011
Trudność

Zapytania

Limit czasowy: 10000 milisekund
Limit pamięciowy: 64000 kilobajtów


Należy przygotować program, który dla zadaniego zbioru punktów Z i wartości "tolerancji" S będzie wykonywał operacje dwóch rodzajów:

  • Usuń zadany punkt ze zbioru Z
  • Znajdź punkt górnolewy zbioru Z
Punkt górnolewy to położony najbardziej na lewo ( posiadający najmniejszą współrzędną x ) punkt spośród tych punktów, których współrzędna y jest mniejsza od współrzędnej y najwyżej położonego punktu w zbiorze o co najwyżej S. Jeśli jest wiele takich punktów, należy wybrać ten z nich, który leży najwyżej ( ma największą współrzędną y ). 

Wejście

W pierwszej linii wejścia znajduje się liczba zestawów testowych Z ( 1 <= Z <= 10 ). Następnie opisywane są kolejne zestawy.

W pierwszej linii opisu pojedynczego zestawu znajdują się dwie oddzielone spacjami liczby naturalne N i S ( 1 <= N <= 105 , 0 <= S <= 109 ) oznaczające początkowy rozmiar zbioru Z i wartość "tolerancji". W kolejnych N liniach znajduje się lista punktów w zbiorze Z w postaci par ( po jednej w linii ) oddzielonych spacjami liczb całkowitych PX i PY (-109 <= PX, PY <= 109) oznaczających punkt o współrzędnych PX, PY. Punkty na liście będą parami różne.

W kolejnej linii opisu pojedynczego zestawu znajduje się liczba naturalna M (1 <= M <= 2*105 ) - liczba operacji do wykonania. Każda z kolejnych M linii jest jednej z dwóch postaci:

  • USUN PX PY
  • ZNAJDZ
Znaczenie poszczególnych operacji jest opisane w treści zadania. Możesz założyć że punkt, który należy usunąć ze zbioru Z w momencie wydania polecenia znajduje się w zbiorze. Możesz założyć, że polecenie "znajdź" nie będzie wywoływane kiedy zbiór Z będzie pusty.

Wyjście

Dla każdego polecenia "znajdź" należy w osobnej linii wypisać współrzędne znalezionego punktu. 

Przykład

Wejście Wyjście
1
5 1
1 1
1 3
2 2
3 2
3 3
7
ZNAJDZ
USUN 1 3
ZNAJDZ
USUN 2 2
ZNAJDZ
USUN 3 3
ZNAJDZ
1 3
2 2
3 3
1 1
Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
3.533335
Twoja ocena: Brak Ocena: 3.5 (15 ocen)

Organizatorzy:

Wrocławski Portal Informatyczny Instytut Informatyki Uniwersytet Wrocławski Wrocław

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com