Guest User

Untitled

a guest
Aug 14th, 2014
377
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.66 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cassert>
  4. #include <algorithm>
  5. #include <cmath>
  6. #include <ctime>
  7. #include <stdint.h>
  8.  
  9. #include <vector>
  10. #include <map>
  11. #include <set>
  12. #include <queue>
  13. #include <cstring>
  14. #include <bitset>
  15. #include <deque>
  16. #include <list>
  17. #include <stack>
  18.  
  19. using namespace std;
  20.  
  21. typedef long long ll;
  22.  
  23. #define mp make_pair
  24. #define pb push_back
  25. #define all(v) (v).begin(), (v).end()
  26. #define foreach(it, v) for(__typeof((v).begin()) it = (v).begin(); it != (v).end(); ++it)
  27. #define sz(v) int((v).size())
  28.  
  29. struct Point {
  30.   int x, y;
  31.  
  32.   int distance(const Point & other) const {
  33.     int dx = x - other.x, dy = y - other.y;
  34.     return dx * dx + dy * dy;
  35.   }
  36. };
  37.  
  38. struct Edge {
  39.   int first_id, second_id, length;
  40.  
  41.   Edge(int first_id, int second_id, int length)
  42.     : first_id(first_id), second_id(second_id), length(length) {}
  43.  
  44.   bool operator < (const Edge & other) const {
  45.     return length > other.length;
  46.   }
  47. };
  48.  
  49. int main() {
  50.   int points_count;
  51.   cin >> points_count;
  52.   ++points_count;
  53.   vector < Point > points(points_count);
  54.   points[0].x = points[0].y = 0;
  55.   for(int i = 1; i < points_count; i++) {
  56.     cin >> points[i].x >> points[i].y;
  57.   }
  58.   vector < Edge > edges;
  59.   edges.reserve(points_count * points_count);
  60.   for(int i = 0; i < points_count; i++) {
  61.     for(int j = 1; j < points_count; j++) {
  62.       if(i != j) {
  63.         edges.pb(Edge(i, j, points[i].distance(points[j])));
  64.       }
  65.     }
  66.   }
  67.   sort(all(edges));
  68.   int result = 0;
  69.   const int inf = 1e9;
  70.   int previous_length = inf;
  71.   vector < int > result_with_greater(points_count, -inf), result_with_same(points_count, -inf);
  72.   int cursor = 0;
  73.   result_with_greater[0] = 0;
  74.   while(cursor < sz(edges)) {
  75.     int current_length = edges[cursor].length;
  76.     //cout << "LENGTH: " << current_length << endl;
  77.     assert(current_length < previous_length);
  78.     vector < int > interesting_points;
  79.     while(cursor < sz(edges) && edges[cursor].length == current_length) {
  80.       const Edge & e = edges[cursor];
  81.       result_with_same[e.second_id] = max(result_with_same[e.second_id], result_with_greater[e.first_id] + 1);
  82.       //cout << "EDGE: " << e.first_id << " " << e.second_id << " " << result_with_greater[e.first_id] << " " << result_with_same[e.second_id] << endl;
  83.       ++cursor;
  84.       interesting_points.pb(e.second_id);
  85.     }
  86.     foreach(it, interesting_points) {
  87.       int i = *it;
  88.       result_with_greater[i] = max(result_with_greater[i], result_with_same[i]);
  89.       result_with_same[i] = -inf;
  90.       result = max(result, result_with_greater[i]);
  91.     }
  92.     previous_length = current_length;
  93.   }
  94.   cout << result << endl;
  95.   return 0;
  96. }
Advertisement
Add Comment
Please, Sign In to add comment