Advertisement
Guest User

Untitled

a guest
May 27th, 2018
61
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.42 KB | None | 0 0
  1. // adam.cpp : Defines the entry point for the console application.
  2. //
  3.  
  4. #include "stdafx.h"
  5. #include <iostream>
  6. #include <vector>
  7. #include <algorithm>
  8. #include <fstream>
  9. #include <utility>
  10. #include <cmath>
  11.  
  12. #define MAX 50001
  13. #define PI 3.141592
  14.  
  15. using namespace std;
  16.  
  17. vector < pair<long long, long long> >large_lantern;
  18. vector < pair<long long, long long> >small_lantern;
  19. vector < pair<double, int> >tangens;
  20.  
  21. vector < pair<long long, long long> >ok;
  22.  
  23. int large_amount;
  24. int small_amount;
  25. int stos[MAX];
  26. int index = 0;
  27.  
  28. fstream plik("sjf.out", std::ios::out);
  29.  
  30. bool det(int A, int B, int C)
  31. {
  32. long long wyznacznik = large_lantern[A].second*large_lantern[B].first + large_lantern[B].second*large_lantern[C].first + large_lantern[C].second*large_lantern[A].first - large_lantern[C].second*large_lantern[B].first - large_lantern[A].second*large_lantern[C].first - large_lantern[B].second*large_lantern[A].first;
  33. if (wyznacznik>0)
  34. return 1;
  35. return 0;
  36. }
  37.  
  38. int wyznacznik_ppl(int A, int B)
  39. {
  40. A = stos[A];
  41. B = stos[B];
  42. long long wyznacznik_ppl = large_lantern[A].second*large_lantern[B].first + large_lantern[B].second*small_lantern[small_lantern.size() - 1].first + small_lantern[small_lantern.size() - 1].second*large_lantern[A].first - large_lantern[A].first*large_lantern[B].second - large_lantern[B].first*small_lantern[small_lantern.size() - 1].second - small_lantern[small_lantern.size() - 1].first*large_lantern[A].second;
  43. if (wyznacznik_ppl >= 0)
  44. return 1;
  45. return 0;
  46. }
  47. int wyznacznik_ppl(int A, int B, int C)
  48. {
  49. long long w_ppl = large_lantern[stos[A]].second*large_lantern[stos[B]].first + large_lantern[stos[B]].second*small_lantern[C].first + small_lantern[C].second*large_lantern[stos[A]].first - small_lantern[C].second*large_lantern[stos[B]].first - large_lantern[stos[A]].second*small_lantern[C].first - large_lantern[stos[B]].second*large_lantern[stos[A]].first;
  50. if (w_ppl >= 0)
  51. return 1;
  52. return 0;
  53. }
  54. int wyznacznik_ppl2(int A, int B)
  55. {
  56. //B = stos[B];
  57. long long w_ppl2 = small_lantern[A].second*small_lantern[small_lantern.size() - 1].first + small_lantern[small_lantern.size() - 1].second*large_lantern[stos[B]].first + large_lantern[stos[B]].second*small_lantern[A].first - large_lantern[stos[B]].second*small_lantern[small_lantern.size() - 1].first - small_lantern[A].second*large_lantern[stos[B]].first - small_lantern[small_lantern.size() - 1].second*small_lantern[A].first;
  58. if (w_ppl2 >= 0)
  59. return 1;
  60. return 0;
  61. }
  62.  
  63. //wrzucamy do stosu
  64. void push(int value)
  65. {
  66. stos[index++] = value;
  67. }
  68.  
  69. //wyrzucamy ze stosu
  70. void del()
  71. {
  72. index--;
  73. }
  74.  
  75. void graham()
  76. {
  77.  
  78. push(0);
  79.  
  80. for (int i = tangens.size() - 1; i >= 0; i--)
  81. {
  82. double value = tangens[i].second;
  83.  
  84. if (index == 2)
  85. push(value);
  86. else
  87. {
  88. while (det(stos[index - 2], stos[index - 1], value) == 0 && index != 1)
  89. del();
  90.  
  91. push(value);
  92. }
  93. }
  94. while (det(stos[index - 2], stos[index - 1], 0) == 0 && index != 1)
  95. del();
  96.  
  97. push(0);
  98. }
  99.  
  100. void sort_alpha(int n)
  101. {
  102. int large_lantern0_Y = large_lantern[0].first;
  103. int large_lantern0_X = large_lantern[0].second;
  104.  
  105. for (int i = 1; i<n; i++)
  106. {
  107. double a = large_lantern[i].second - large_lantern0_X;
  108. double b = large_lantern[i].first - large_lantern0_Y;
  109. double tang = a / b * 180 / PI;
  110. tangens.push_back(make_pair(tang, i));
  111. }
  112. sort(tangens.begin(), tangens.end());
  113.  
  114. int ind = 1;
  115. }
  116. void ppl()
  117. {
  118. for (int i = 0; i<small_amount; i++)
  119. {
  120. int przeciecia = 0;
  121. for (int j = 0; j<index - 1; j++)
  122. {
  123.  
  124. if (wyznacznik_ppl(j, j + 1) != wyznacznik_ppl(j, j + 1, i)
  125. && wyznacznik_ppl2(i, j) != wyznacznik_ppl2(i, j + 1))
  126. przeciecia++;
  127. }
  128.  
  129. if (przeciecia % 2 != 0)
  130. {
  131. ok.push_back(make_pair(small_lantern[i].second, small_lantern[i].first));
  132. }
  133. }
  134.  
  135. plik << ok.size() << endl;
  136. }
  137.  
  138.  
  139. void read(string nazwa)
  140. {
  141. fstream file;
  142. file.open(nazwa, ios::in);
  143.  
  144.  
  145. double x, y;
  146.  
  147. file >> large_amount;
  148. for (int i = 0; i<large_amount; i++)
  149. {
  150. file >> x;
  151. file >> y;
  152. large_lantern.push_back(make_pair(y, x));
  153. }
  154. file >> small_amount;
  155. for (int i = 0; i<small_amount; i++)
  156. {
  157. file >> x;
  158. file >> y;
  159. small_lantern.push_back(make_pair(y, x));
  160. }
  161. small_lantern.push_back(make_pair(pow(2, 30), pow(2, 30)));
  162. sort(large_lantern.begin(), large_lantern.end());
  163. sort(small_lantern.begin(), small_lantern.end());
  164.  
  165. sort_alpha(large_amount);
  166. graham();
  167. ppl();
  168.  
  169. }
  170.  
  171. int main()
  172. {
  173. read("ala.in");
  174.  
  175. return 0;
  176. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement