fork(3) download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. void Quicksort(int ** tab, int low, int high)
  5. {
  6. 	int wall = low;
  7. 	int fN, fW;			// zmienne pomocnicze N - number, W - wartość
  8.  
  9.  
  10. 	for (int i = low; i <= high; i++)
  11. 	{
  12. 		if (tab[1][i] <= tab[1][high])
  13. 		{
  14. 			fN = tab[0][i];
  15. 			fW = tab[1][i];
  16. 			tab[0][i] = tab[0][wall];
  17. 			tab[1][i] = tab[1][wall];
  18. 			tab[0][wall] = fN;
  19. 			tab[1][wall] = fW;
  20. 			wall++;
  21. 		}
  22. 	}								
  23.  
  24. 	if (wall < high)
  25. 		Quicksort(tab, wall, high);
  26.  
  27. 	if (wall - 2 > low)
  28. 		Quicksort(tab, low, wall - 2);
  29. }
  30.  
  31. void zgrabna_funkcja(int ** tab, int wymiar)
  32. {
  33. 	int i = 0, j = 0, k = 0, l = 0;
  34.  
  35. 	for (int num = 0; num < wymiar / 3; num++)
  36. 	{
  37. 		while (tab[4][tab[0][i] - 1] == 0)		// X malejąco
  38. 			i++;
  39. 		tab[0][num] = tab[0][i];
  40.  
  41. 		while (tab[4][tab[1][j] - 1] == 0)		// X rosnąco
  42. 			j++;
  43. 		tab[1][num] = tab[1][j];
  44.  
  45. 		while (tab[4][tab[2][k] - 1] == 0)		// Y malejąco
  46. 			k++;
  47. 		tab[2][num] = tab[2][k];
  48.  
  49. 		while (tab[4][tab[3][l] - 1] == 0)		// Y rosnąco
  50. 			l++;
  51. 		tab[3][num] = tab[3][l];
  52.  
  53. 		tab[4][tab[0][i] - 1] = 0;
  54. 		tab[4][tab[1][j] - 1] = 0;
  55. 		tab[4][tab[2][k] - 1] = 0;
  56. 		tab[4][tab[3][l] - 1] = 0;
  57. 	}
  58. }
  59.  
  60. void ostatnie_porzadki(int ** tab, int wymiar)
  61. {
  62. 	int supp;
  63. 	for (int i = 0; i < wymiar / 3; i++)
  64. 		for (int k = 0; k < 3; k++)
  65. 			for (int j = 0; j < 3; j++)
  66. 				if (tab[j][i] > tab[j + 1][i])
  67. 				{
  68. 					supp = tab[j][i];
  69. 					tab[j][i] = tab[j + 1][i];
  70. 					tab[j + 1][i] = supp;
  71. 				}
  72.  
  73. }
  74.  
  75. void daj_glos(int ** tab, int wymiar)
  76. {
  77. 	for (int i = 0; i < wymiar / 3; i++)
  78. 	{
  79. 		cout << tab[0][i] << " ";
  80. 		if (tab[1][i] > tab[0][i])
  81. 			cout << tab[1][i] << " ";
  82. 		if (tab[2][i] > tab[1][i])
  83. 			cout << tab[2][i] << " ";
  84. 		if (tab[3][i] > tab[2][i])
  85. 			cout << tab[3][i];
  86.  
  87. 		cout << endl;
  88. 	}
  89. }
  90.  
  91. void f_delete(int ** tabX, int ** tabY, int ** tab5)
  92. {
  93. 	delete[] tabX[0];
  94. 	delete[] tabX[1];
  95. 	delete[] tabX;
  96. 	delete[] tabY[0];
  97. 	delete[] tabY[1];
  98. 	delete[] tabY;
  99. 	delete[] tab5[0];
  100. 	delete[] tab5[1];
  101. 	delete[] tab5[2];
  102. 	delete[] tab5[3];
  103. 	delete[] tab5[4];
  104. 	delete[] tab5;
  105. }
  106.  
  107. int main()
  108. {
  109. 	int t;									// program ma policzyć t zadań testowych
  110. 	cin >> t;
  111. 	while (t--)
  112. 	{
  113. 		int LiczbaPunktow;					// każde z nich składa się LiczybyPunktow 
  114. 		cin >> LiczbaPunktow;				// o współrzędnych X i Y
  115. 		int& wymiar = LiczbaPunktow;
  116.  
  117. 		int ** tabX = new int *[2];			// tworzę dwie niezależne tablice 
  118. 		tabX[0] = new int[wymiar];			// tablica X
  119. 		tabX[1] = new int[wymiar];
  120. 		int ** tabY = new int *[2];			// tablica Y
  121. 		tabY[0] = new int[wymiar];			// które przechodują dwie wartości 
  122. 		tabY[1] = new int[wymiar];			// numer punktu i wartość wpółrzędnej X lub Y
  123.  
  124. 		for (int i = 0; i < wymiar; i++)
  125. 		{
  126. 			tabX[0][i] = i + 1;				// nadanie numerów punktom X
  127. 			tabY[0][i] = i + 1;				// nadanie numerów punktom Y
  128. 			cin >> tabX[1][i] >> tabY[1][i];			// wczytanie współrzędnych
  129. 		}
  130.  
  131. 		Quicksort(tabX, 0, wymiar - 1);		// posortowanie tablicy X 
  132. 		Quicksort(tabY, 0, wymiar - 1);		// posortowanie tablicy Y
  133.  
  134. 		int ** tab5 = new int *[5]; 	// deklaracja tablicy, w której przechowywane będę
  135. 		for (int i = 0; i < 5; i++)		// tylko numery punktów, ale w 4 kategoriach
  136. 			tab5[i] = new int[wymiar];
  137.  
  138. 		for (int i = 0; i < wymiar; i++)
  139. 		{
  140. 			tab5[0][i] = tabX[0][wymiar - 1 - i];		// X malejąco
  141. 			tab5[1][i] = tabX[0][i];					// X rosnąco
  142. 			tab5[2][i] = tabY[0][wymiar - 1 - i];		// Y malejąco
  143. 			tab5[3][i] = tabY[0][i];					// Y rosnąco
  144. 			tab5[4][i] = 1;								// informacja o wykorzystaniu punktu do budowy trójkąta 
  145. 		}												// 0 - niedostępne, 1 - dostępne
  146.  
  147. 		zgrabna_funkcja(tab5, wymiar);		// sortuje tablicę w taki sposób, aby żaden punkt 
  148. 											// nie został wykorzystany do budowy więcej niż jednego trójkąta
  149. 		ostatnie_porzadki(tab5, wymiar);	// funkcja pomocnicza ustawiająca punkty w kolejności według ich numerów
  150.  
  151. 		daj_glos(tab5, wymiar);				// wypisuje kolejne trójki numerów punktów
  152. 											// które składają się na trójkąty ostrokątne
  153. 		f_delete(tabX, tabY, tab5);			// funkcja istniejąca ze względu na aspekt estetyczny
  154.  
  155. 		if (t > 0)
  156. 			cout << endl;
  157. 	}
  158.  
  159. 	cin.get();
  160. 	cin.get();
  161. 	return 0;
  162. }
Success #stdin #stdout 0s 4416KB
comments (?)
stdin
copy 
2
3
0 0
1 2
2 1
6
-2 0
2 0
1 1
-1 1
0 3
0 4
stdout
copy 
1 2 3

1 2 6
3 4 5
https://ideone.com/J5hUum
language:
C++ (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!