1. /*   6.   Dany jest zbiór S punktów na płaszczyźnie. Punkt p[is in]S
2.       nazywamy punktem separującym, jeżeli można rozbić zbiór S-{p}
3.       pozostałych punktów na dwa rozłączne podzbiory A i B takie,
4.       że wszystkie punkty podzbioru A są dominowane przez punkt p
5.       zaś wszystkie punkty podzbioru B dominują punkt p. Podzbiory
6.       A lub B mogą być puste. Podać algorytm (i ocenić jego złożoność)
7.       wyznaczania punktu separującego.
8. */
9.  
10. int FindSplitPoints(Point S[], int n)
11. {
12.    /*   sortuję tablicę punktów według zadanej metryki, tzn.
13.       P1>P2 <=> [ x1>x2 v (x1==x2 ^ y1>y2) ].
14.       Zakładam, że sortowanie odbywa się ze złożonością nlogn.
15.    */
16.    sort(S[]);            
17.    
18.    /*   pierwszy punkt tymczasowo uznaję za separujący   */
19.    bool found=true;
20.    int index = 0;
21.    
22.    int boundX=S[0].x;
23.    int boundY=S[0].y;
24.  
25.    for(int i=1;i<n;i++)
26.    {
27.       /*   Jeśli punkt leży na bieżącej granicy x trzeba granicę y przesunąć
28.          wyżej. Z całą pewnością nie znaleźliśmy w takim układzie punktu
29.          separującego.
30.       */
31.       if(S[i].x==boundX)   //y>boundY
32.       {
33.          found=false;
34.          boundX=S[i].x;
35.          boundY=S[i].y;
36.       }
37.       /*   Jeśli punkt leży poniżej (lub na) bieżącej granicy y, ta granica
38.          pozostaje taka sama. Granica x przesuwa się zaś do tego punktu.
39.          Z całą pewnością nie znaleźliśmy jeszcze punktu separującego.
40.       */
41.       else if(S[i].y<=boundY)
42.       {
43.          found=false;
44.          boundX=S[i].x;
45.       }
46.       /*   Jeśli punkt leży powyżej obu granic - mamy nowy potencjalny punkt
47.          separujący lub utrzymujemy dotychczasowy.
48.       */
49.       else
50.       {
51.          if (found==true) continue;
52.          else
53.          {
54.             found=true;
55.             index=i;
56.          }
57.       }
58.    }
59.    if (found) return index;
60.    return -1;
61. }