Guest User

Untitled

a guest
Feb 25th, 2018
87
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.96 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using vi = vector<int>;
  4.  
  5. struct Point {
  6. public:
  7. Point() : _x(0), _y(0) {}
  8.  
  9. Point(int x, int y) : _x(x), _y(y) {}
  10.  
  11. bool operator==(const Point& rhs) const {
  12. return x() == rhs.x() && y() == rhs.y();
  13. }
  14.  
  15. bool operator!=(const Point& rhs) const { return !this->operator==(rhs); }
  16.  
  17. bool operator<(const Point& rhs) const {
  18. if (x() != rhs.x()) return x() < rhs.x();
  19. return y() < rhs.y();
  20. }
  21.  
  22. int x() const { return _x; }
  23.  
  24. int y() const { return _y; }
  25.  
  26. int cuadrant() const { return int(x() >= 0) * 2 + int(y() >= 0); }
  27.  
  28. long long sqr_dst_to(const Point& rhs) const {
  29. long long xx = rhs.x() - x();
  30. long long yy = rhs.y() - y();
  31. return xx * xx + yy * yy;
  32. }
  33.  
  34. private:
  35. int _x, _y;
  36. };
  37.  
  38. struct Lizard {
  39. Point location;
  40. int height;
  41.  
  42. // sort data
  43. int cuadrant;
  44. Point slope_to_tv;
  45. long long sqr_dist_to_tv;
  46.  
  47. bool is_grouped_with(const Lizard& rhs) const {
  48. return cuadrant == rhs.cuadrant && slope_to_tv == rhs.slope_to_tv;
  49. }
  50. };
  51.  
  52. bool operator<(const Lizard& lhs, const Lizard& rhs) {
  53. if (lhs.cuadrant != rhs.cuadrant) {
  54. return lhs.cuadrant < rhs.cuadrant;
  55. }
  56.  
  57. if (lhs.slope_to_tv != rhs.slope_to_tv) {
  58. return lhs.slope_to_tv < rhs.slope_to_tv;
  59. }
  60.  
  61. return lhs.sqr_dist_to_tv < rhs.sqr_dist_to_tv;
  62. }
  63.  
  64. vector<int> build_lis(const vector<int>& sequence) {
  65. vector<int> result;
  66.  
  67. for (int x : sequence) {
  68. vector<int>::iterator it = lower_bound(result.begin(), result.end(), x);
  69. if (it == result.end())
  70. result.push_back(x);
  71. else
  72. *it = x;
  73. }
  74.  
  75. return result;
  76. }
  77.  
  78. int gcd(int a, int b) {
  79. while (b != 0) {
  80. int c = a % b;
  81. a = b;
  82. b = c;
  83. }
  84. return a;
  85. }
  86.  
  87. Point make_slope(Point p1, Point p2) {
  88. int yy = p2.y() - p1.y();
  89. int xx = p2.x() - p1.x();
  90.  
  91. int g = gcd(yy, xx);
  92. yy /= g;
  93. xx /= g;
  94.  
  95. return Point(xx, yy);
  96. }
  97.  
  98. int solve(const Point& tv, const vector<Lizard>& lizards) {
  99. const int n = (int)lizards.size();
  100.  
  101. int result = 0;
  102. vector<int> group;
  103.  
  104. auto process_group = [&]() {
  105. if (group.size() == 0) return;
  106. result += build_lis(group).size();
  107. };
  108.  
  109. for (int i = 0; i < n; ++i) {
  110. const Lizard& current = lizards[i];
  111.  
  112. bool grouped_with_last = (i > 0 && lizards[i - 1].is_grouped_with(current));
  113. if (!grouped_with_last) {
  114. process_group();
  115. group.clear();
  116. }
  117.  
  118. group.push_back(current.height);
  119. }
  120.  
  121. process_group();
  122.  
  123. return result;
  124. }
  125.  
  126. int main() {
  127. ios_base::sync_with_stdio(false);
  128. cin.tie(nullptr);
  129.  
  130. int x, y;
  131.  
  132. while (cin >> x >> y) {
  133. Point tv(x, y);
  134.  
  135. int n;
  136. cin >> n;
  137.  
  138. vector<Lizard> lizards(n);
  139. for (auto&& lizard : lizards) {
  140. cin >> x >> y >> lizard.height;
  141. lizard.location = Point(x, y);
  142. lizard.cuadrant = Point(tv.x() - x, tv.y() - y).cuadrant();
  143. lizard.slope_to_tv = make_slope(lizard.location, tv);
  144. lizard.sqr_dist_to_tv = tv.sqr_dst_to(lizard.location);
  145. }
  146. sort(begin(lizards), end(lizards));
  147.  
  148. cout << solve(tv, lizards) << endl;
  149. }
  150.  
  151. return 0;
  152. }
Add Comment
Please, Sign In to add comment