Algorytm generuje kolejne punkty otoczki wypukłej w C++.
Program
#include<bits/stdc++.h> using namespace std; #define pkt pair<int, int> //start - punkt, wzgledem ktorego bedziemy sortowac pair <int, int> start; stack<pkt> otoczka; //sprawdzam, w ktorym kierunku skrecam //jesli zwracany wynik jest ujemny, to w lewo, jesli dodatni to w prawo, //jesli zero to ide prosto int iloczyn_wektorowy(pkt X, pkt Y, pkt Z) { int x1 = Z.first - X.first, y1 = Z.second - X.second, x2 = Y.first - X.first, y2 = Y.second - X.second; return x1*y2 - x2*y1; } //zwracam stos z wierzcholkami otoczki stack<pkt > buduj_otoczke(vector <pkt > P) { stack<pkt > stos; stos.push(P[0]); pkt X = P[0], Y = P[1]; for(int i=2; i<P.size(); i++) { // dopóki skręcam w prawo lub ide prosto //usuwam niepotrzebne wierzcholki ze stosu while(iloczyn_wektorowy(X, Y, P[i])>=0) { Y = X; stos.pop(); if(stos.empty())break; X = stos.top(); //X <- P[0] } stos.push(Y); X = Y; Y = P[i]; } return stos; } bool porownaj(pkt A, pkt B) { //ustawiam wierzcholek startowy na poczatku tablicy if(A==start)return 1; if(B==start)return 0; //------------------------------------------------- //jesli dla dwoch punkow kat jest taki sam, to najpierw //wez ten, ktory ma mniejsza wspolrzedna x if((A.second-start.second)*(B.first-start.first) == (A.first-start.first)*(B.second-start.second)) return A.first<B.first; return (A.second-start.second)*(B.first-start.first) < (A.first-start.first)*(B.second-start.second); } int main() { int n; cin>>n; vector <pkt > P(n); for(int i=0; i<n; i++) { cin>>P[i].first>>P[i].second; //P(x, y) = (P.first, P.second) //szukam wieszcholka najnizej polozonego //a w przypadku remisu, najbardziej na lewo if(i==0) start = P[i]; else if(P[i].second == start.second) start.first = min(P[i].first, start.first); else if(P[i].second < start.second) start = P[i]; //------------------------------------------------ } //sortowanie katowe wzgledem punktu polozonego //najbardziej na dole, a w przypadku remisu //najbardziej na lewo sort(P.begin(), P.end(), porownaj); P.push_back(start); stack<pkt > stos = buduj_otoczke(P); //wypisanie wierzcholka startowego cout<<start.first<<' '<<start.second<<endl; //wypisanie kolejnych wierzcholkow otoczki wypuklej while(!stos.empty()) { cout<<stos.top().first<<' '<<stos.top().second<<endl; stos.pop(); } return 0; } |
Dane wejściowe:
W pierwszym wierszu jedna liczba naturalna n (n > 2) określająca liczbę punktów.
W kolejnych n wierszach współrzędne całkowite punktów (przy założeniu, że przynajmniej trzy nie są współliniowe oraz punkty się nie powtarzają).
Wyjście:
Wypisanie kolejnych punktów otoczki wypukłej.
Przykład:
Wejście:
7 2 3 1 1 -2 5 0 9 -3 2 1 0 9 8
Wyjście:
1 0 -3 2 -2 5 0 9 9 8 1 0