Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdio>
- #include <cassert>
- #include <algorithm>
- #include <cmath>
- #include <ctime>
- #include <stdint.h>
- #include <vector>
- #include <map>
- #include <set>
- #include <queue>
- #include <cstring>
- #include <bitset>
- #include <deque>
- #include <list>
- #include <stack>
- using namespace std;
- typedef long long ll;
- #define mp make_pair
- #define pb push_back
- #define all(v) (v).begin(), (v).end()
- #define foreach(it, v) for(__typeof((v).begin()) it = (v).begin(); it != (v).end(); ++it)
- #define sz(v) int((v).size())
- struct Point {
- int x, y;
- int distance(const Point & other) const {
- int dx = x - other.x, dy = y - other.y;
- return dx * dx + dy * dy;
- }
- };
- struct Edge {
- int first_id, second_id, length;
- Edge(int first_id, int second_id, int length)
- : first_id(first_id), second_id(second_id), length(length) {}
- bool operator < (const Edge & other) const {
- return length > other.length;
- }
- };
- int main() {
- int points_count;
- cin >> points_count;
- ++points_count;
- vector < Point > points(points_count);
- points[0].x = points[0].y = 0;
- for(int i = 1; i < points_count; i++) {
- cin >> points[i].x >> points[i].y;
- }
- vector < Edge > edges;
- edges.reserve(points_count * points_count);
- for(int i = 0; i < points_count; i++) {
- for(int j = 1; j < points_count; j++) {
- if(i != j) {
- edges.pb(Edge(i, j, points[i].distance(points[j])));
- }
- }
- }
- sort(all(edges));
- int result = 0;
- const int inf = 1e9;
- int previous_length = inf;
- vector < int > result_with_greater(points_count, -inf), result_with_same(points_count, -inf);
- int cursor = 0;
- result_with_greater[0] = 0;
- while(cursor < sz(edges)) {
- int current_length = edges[cursor].length;
- //cout << "LENGTH: " << current_length << endl;
- assert(current_length < previous_length);
- vector < int > interesting_points;
- while(cursor < sz(edges) && edges[cursor].length == current_length) {
- const Edge & e = edges[cursor];
- result_with_same[e.second_id] = max(result_with_same[e.second_id], result_with_greater[e.first_id] + 1);
- //cout << "EDGE: " << e.first_id << " " << e.second_id << " " << result_with_greater[e.first_id] << " " << result_with_same[e.second_id] << endl;
- ++cursor;
- interesting_points.pb(e.second_id);
- }
- foreach(it, interesting_points) {
- int i = *it;
- result_with_greater[i] = max(result_with_greater[i], result_with_same[i]);
- result_with_same[i] = -inf;
- result = max(result, result_with_greater[i]);
- }
- previous_length = current_length;
- }
- cout << result << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment