algorytm.org

Implementacja w C/C++

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Znajdowanie wypukłej otoczki (algorytm Grahama) - Implementacja w C/C++
Ocena użytkownikóww: *****  / 9
SłabyŚwietny
Nadesłany przez Michał Knasiecki, 03 sierpnia 2005 01:00
Kod przedstawiony poniżej przedstawia główną część rozwiązania problemu.
Pobierz pełne rozwiązanie.

Jeżeli nie odpowiada Ci sposób formatowania kodu przez autora skorzystaj z pretty printer'a i dostosuj go automatycznie do siebie.

graham.cpp:
/********************************************************************************
*                                                                    		*
*	Algorytm Grahama konstrukcji wypukłej otoczki				*
*  	Plik pobrany ze strony:			www.algorytm.org                *
*	Opracowal:				Michal Knasiecki		*
*                                                                    		*
*********************************************************************************/

/*Uwagi:

1. W poniższej implementacji posłużono się biblioteką STL, która
   zawiera szablon wektora oraz stosu.
   Jeżeli twój kompilator nie posiada tej biblioteki możesz zastąpić
   wektor tablicą oraz wykorzystać własnąimplementacjęstosu.

2. Dane wejściowe muszą być w postaci uporządkowanej (patrz strona WWW).

3. Wynik jest wypisywany w porządku zgodnym z kierunkiem ruchu wskazówek zegara.
*/

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>

#include <stack>
#include <vector>

using namespace std;
typedef struct
	{
   int x;
   int y;
   } Tpunkt;

//Funkcja oblicza wyznacznik macierzy 3x3 (metodą Sarrusa)
int det(Tpunkt p1, Tpunkt p2, Tpunkt p3){
return p1.x*p2.y + p2.x*p3.y + p3.x*p1.y - p3.x*p2.y - p1.x*p3.y - p2.x*p1.y;
}


//Funkcja sprawdza, czy przechodząc do punktu p3 skręcamy w prawo (1), czy w lewo (0)
int skret_w_prawo(stack<Tpunkt,vector<Tpunkt> > S,Tpunkt p3){
Tpunkt p2;
Tpunkt p1;

//Pobieramy ze szczytu stosu punkt p2 oraz punkt p1, bedacy tuż pod szczytem
p2=S.top();
S.pop();
p1=S.top();
S.push(p2);

//Punkt p3 leży po lewej stronie wektora p1->p2
if (det(p1,p2,p3)>0)
	return 0;

//Punkt p3 leży po prawej stronie wektora p1->p2
if (det(p1,p2,p3)<0)
	return 1;
}

void main(void){
//Lista wejściowa (uporządkowana: czyt. na stronie)
vector<Tpunkt> Q;

//Stos punktów, na końcu zawiera wynik
stack<Tpunkt,vector<Tpunkt> > S;

Tpunkt punkt;
int liczba_punktow;

//Przykładowa instancja danych (zob. przyklad.gif)

liczba_punktow=10;
// punkt a
punkt.x=1;
punkt.y=1;
Q.push_back(punkt);
// punkt b
punkt.x=6;
punkt.y=2;
Q.push_back(punkt);
// punkt c
punkt.x=3;
punkt.y=2;
Q.push_back(punkt);
// punkt d
punkt.x=4;
punkt.y=3;
Q.push_back(punkt);
// punkt e
punkt.x=5;
punkt.y=6;
Q.push_back(punkt);
// punkt f
punkt.x=3;
punkt.y=5;
Q.push_back(punkt);
// punkt g
punkt.x=4;
punkt.y=8;
Q.push_back(punkt);
// punkt h
punkt.x=2;
punkt.y=6;
Q.push_back(punkt);
// punkt i
punkt.x=1;
punkt.y=7;
Q.push_back(punkt);
// punkt j
punkt.x=0;
punkt.y=4;
Q.push_back(punkt);

//Początek algorytmu

//Umieszczamy 3 pierwsze punkty na stosie
S.push(Q[0]);
S.push(Q[1]);
S.push(Q[2]);

for (int i=3;i<liczba_punktow;i++){
	while (skret_w_prawo(S,Q[i])==1)
   	S.pop();
   S.push(Q[i]);
}


printf("Punkty tworzace wypukla otoczke: \n");
while (!(S.empty()))
{
punkt=S.top();
S.pop();
printf("(%d,%d) ",punkt.x,punkt.y);
}
printf("\nDowolny klawisz...");
getch();
return;
}

Komentarze
photo
-15 # Martyna1992 2012-05-02 18:56
Dostanę ten program w języku C ?
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-2 # codekaizen 2014-10-31 20:33
Czy ten kod ma prawo działać skoro do funkcji skret_w_prawo() jest przenoszony stos przez wartość a nie przez referencję? No chyba nie - C++ to nie Java.
No i po co dwa razy obliczać wyznacznik skoro można raz?
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz