Advertisement
Guest User

Untitled

a guest
Mar 24th, 2017
58
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.14 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <math.h>
  5. #include <utility>
  6. #include <cstdlib>
  7. #include <cmath>
  8. #include <string>
  9.  
  10. using namespace std;
  11.  
  12.  
  13. class Sortuj_X;
  14. class Sortuj_Y;
  15. class Punkt
  16. {
  17. public:
  18. string nazwa;
  19. double stopnie_szerokosc;
  20. double stopnie_dlugosc;
  21.  
  22.  
  23. /*void stworz(string nazwa,
  24. int stopnie_szerokosc,
  25. int minuty_szerokosc,
  26. string PLN_PLD,
  27. int stopnie_dlugosc,
  28. int minuty_dlugosc,
  29. string WSCH_ZACH)*/
  30. void stworz(){
  31. int minuty_szerokosc;
  32. string PLN_PLD;
  33. int minuty_dlugosc;
  34. string WSCH_ZACH;
  35. cin >> nazwa >> stopnie_szerokosc >> minuty_szerokosc >> PLN_PLD >> stopnie_dlugosc >> minuty_dlugosc >> WSCH_ZACH;
  36.  
  37. stopnie_szerokosc = stopnie_szerokosc + (minuty_szerokosc/60.0f);
  38. stopnie_dlugosc = stopnie_dlugosc + (minuty_dlugosc/60.0f);
  39. stopnie_szerokosc = stopnie_szerokosc * M_PI/180.0f;
  40. stopnie_dlugosc = stopnie_dlugosc * M_PI/180.0f;
  41. if(PLN_PLD == "S")
  42. stopnie_dlugosc *= -1;
  43.  
  44. if(WSCH_ZACH =="W")
  45. stopnie_szerokosc *= -1;
  46. }
  47.  
  48.  
  49.  
  50. };
  51. double obwod_sfery;
  52. const double _PI = 3.14;
  53. double _krzywa = (40075,704/360);
  54. const double _pol = 180;
  55. Punkt *temp = new Punkt;
  56. double najmniejszy = INFINITY;
  57. double promien = (M_PI+M_PI);
  58.  
  59. class Sortuj_X
  60. {
  61. public:
  62. bool operator()(Punkt const &a, Punkt const &b)
  63. {
  64. return a.stopnie_szerokosc < b.stopnie_szerokosc;
  65. }
  66.  
  67. };
  68.  
  69. class Sortuj_Y
  70. {
  71. public:
  72. bool operator()(Punkt const &a, Punkt const &b)
  73. {
  74. return a.stopnie_dlugosc < b.stopnie_dlugosc;
  75. }
  76.  
  77. };
  78.  
  79.  
  80.  
  81.  
  82. double znajdzOrtodromadlaTab(Punkt x, Punkt y)
  83. {
  84. double ortodroma;
  85.  
  86.  
  87.  
  88. //ortodroma = sqrt(pow(y.stopnie_szerokosc - x.stopnie_szerokosc, 2) + pow((cos((x.stopnie_szerokosc * _PI)) / _pol) * (y.stopnie_dlugosc - x.stopnie_dlugosc), 2))* _krzywa;
  89. //ortodroma = acos( (sin(szerokosc_D1) * sin(szerokosc_D2)));// + ( cos(pkt[i].stopnie_szerokosc) * cos(pkt[i+1].stopnie_szerokosc) * cos(pkt[i].stopnie_dlugosc - pkt[i+1].stopnie_dlugosc) ) ) ;
  90. ortodroma = acos( (sin(x.stopnie_szerokosc) * (sin(y.stopnie_szerokosc))) + (cos(x.stopnie_szerokosc) * cos(y.stopnie_szerokosc) * cos(x.stopnie_dlugosc - y.stopnie_dlugosc) ) ) *promien;
  91.  
  92. return ortodroma;
  93. }
  94.  
  95.  
  96.  
  97. void zamien(Punkt *tab, int i, int j)
  98. {
  99.  
  100. temp = &tab[i];
  101. tab[i] = tab[j];
  102. tab[j] = *temp;
  103.  
  104.  
  105. }
  106.  
  107. pair<Punkt, Punkt> punkty;
  108.  
  109. double dlaPojedynczych(Punkt *tab, int rozmiar)
  110. {
  111. // DUZA LICZBA
  112. for(int i =0; i<rozmiar; ++i)
  113. {
  114. for(int j=i+1; j<rozmiar; ++j)
  115. {
  116.  
  117.  
  118. if(znajdzOrtodromadlaTab(tab[i], tab[j]) < najmniejszy)
  119. {
  120. najmniejszy = znajdzOrtodromadlaTab(tab[i], tab[j]);
  121.  
  122. punkty = make_pair(tab[i], tab[j]);
  123. }
  124. }
  125. }
  126.  
  127. return najmniejszy;
  128. }
  129.  
  130. double minFunkcja(double x, double y)
  131. {
  132. if(x < y)
  133. return x;
  134. if(y < x)
  135. return y;
  136. }
  137.  
  138. double funkcjaRoznica(double a, double b)
  139. {
  140. double roznica;
  141. roznica = a-b;
  142. return roznica;
  143. }
  144.  
  145. double punktyPasek(Punkt *pasek, int rozmiar, double odleglosc)
  146. {
  147. najmniejszy = odleglosc;
  148. sort(pasek , pasek+rozmiar, Sortuj_Y() );
  149.  
  150. for(int i = 0; i < rozmiar; ++i){
  151.  
  152. for(int j = i+1; j < rozmiar && (funkcjaRoznica(pasek[j].stopnie_dlugosc, pasek[i].stopnie_dlugosc) ) < najmniejszy; ++j)
  153. {
  154. if(znajdzOrtodromadlaTab(pasek[i], pasek[j])< najmniejszy)
  155. {
  156. najmniejszy = znajdzOrtodromadlaTab(pasek[i], pasek[j]);
  157.  
  158. }
  159. }
  160. }
  161. return najmniejszy;
  162. }
  163.  
  164. double najblizejWykonaj(Punkt *tab, int rozmiar)
  165. {
  166.  
  167. if( rozmiar <= 15) {
  168. return dlaPojedynczych(tab, rozmiar);
  169. }
  170.  
  171. int mid = rozmiar/2;
  172. Punkt midPoint = tab[mid];
  173.  
  174. double dl = najblizejWykonaj(tab, mid);
  175. double dr = najblizejWykonaj(tab + mid, rozmiar-mid);
  176.  
  177. double odleglosc = minFunkcja(dl, dr);
  178.  
  179. Punkt pasek[rozmiar];
  180. int j;
  181. j = 0;
  182.  
  183. for(int i= 0; i<rozmiar; i++)
  184. {
  185. if(abs(tab[i].stopnie_szerokosc = midPoint.stopnie_szerokosc)<odleglosc)
  186. {
  187. pasek[j] = tab[i], j++;
  188. }
  189. }
  190.  
  191. return minFunkcja(odleglosc, punktyPasek(pasek, j, odleglosc));
  192. }
  193.  
  194.  
  195. double wykonajFun(Punkt *tab, int rozmiar)
  196. {
  197. sort(tab, tab+rozmiar, Sortuj_X());
  198. return najblizejWykonaj(tab, rozmiar);
  199. }
  200.  
  201.  
  202.  
  203.  
  204.  
  205. int main()
  206. {
  207. int liczba_punktow;
  208. cin >> liczba_punktow;
  209. double obwod_sfery1;
  210. cin >> obwod_sfery1;
  211.  
  212.  
  213. //vector<Punkt> pkt;
  214.  
  215. Punkt *tab = new Punkt[liczba_punktow];
  216. for(int i =0 ; i< liczba_punktow; i++)
  217. {
  218. Punkt *p = new Punkt;
  219. p->stworz();
  220. tab[i] = *p;
  221. }
  222.  
  223. sort(tab, tab+liczba_punktow, Sortuj_X());
  224.  
  225. wykonajFun(tab, liczba_punktow);
  226. if(punkty.first.nazwa < punkty.second.nazwa)
  227. cout << punkty.first.nazwa << " " << punkty.second.nazwa;
  228. else
  229. cout << punkty.second.nazwa << " " << punkty.first.nazwa;
  230.  
  231.  
  232.  
  233.  
  234.  
  235.  
  236. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement