/*   6.   Dany jest zbiór S punktów na płaszczyźnie. Punkt p[is in]S
      nazywamy punktem separującym, jeżeli można rozbić zbiór S-{p}
      pozostałych punktów na dwa rozłączne podzbiory A i B takie,
      że wszystkie punkty podzbioru A są dominowane przez punkt p
      zaś wszystkie punkty podzbioru B dominują punkt p. Podzbiory
      A lub B mogą być puste. Podać algorytm (i ocenić jego złożoność)
      wyznaczania punktu separującego.
*/

int FindSplitPoints(Point S[], int n)
{
   /*   sortuję tablicę punktów według zadanej metryki, tzn.
      P1>P2 <=> [ x1>x2 v (x1==x2 ^ y1>y2) ].
      Zakładam, że sortowanie odbywa się ze złożonością nlogn.
   */
   sort(S[]);            
   
   /*   pierwszy punkt tymczasowo uznaję za separujący   */
   bool found=true;
   int index = 0;
   
   int boundX=S[0].x;
   int boundY=S[0].y;

   for(int i=1;i<n;i++)
   {
      /*   Jeśli punkt leży na bieżącej granicy x trzeba granicę y przesunąć
         wyżej. Z całą pewnością nie znaleźliśmy w takim układzie punktu
         separującego.
      */
      if(S[i].x==boundX)   //y>boundY
      {
         found=false;
         boundX=S[i].x;
         boundY=S[i].y;
      }
      /*   Jeśli punkt leży poniżej (lub na) bieżącej granicy y, ta granica
         pozostaje taka sama. Granica x przesuwa się zaś do tego punktu.
         Z całą pewnością nie znaleźliśmy jeszcze punktu separującego.
      */
      else if(S[i].y<=boundY)
      {
         found=false;
         boundX=S[i].x;
      }
      /*   Jeśli punkt leży powyżej obu granic - mamy nowy potencjalny punkt
         separujący lub utrzymujemy dotychczasowy.
      */
      else
      {
         if (found==true) continue;
         else
         {
            found=true;
            index=i;
         }
      }
   }
   if (found) return index;
   return -1;
}