At the point (0, 0) stand a pawn. Pawn has n allowed movements. Each one is desribed as a vector of integer coordinates. Pawn can do each movement only once in any order. Vectors may repeat and then the pawn may use each of them.
Our goal is to count maximum distance from point (0, 0) to the the fatherst located point - Euclidean distance.
Input:
The first line cantains one positive number n denoting number of possible moves by the pawn.
Next n lines contain two positive numbers xi, yi (-104 ≤ xi, yi ≤ 104) separated by a single space and representing vector [xi, yi] desribing possible movement of the pawn.
Output:
Program has to print the number denoting sqaure distance from point (0, 0) to farthest point to which he can jump.
Example:
For the input:
5
2 -2
-2 -2
0 2
3 1
-3 1
Correct answer is:
26
Link to example
Explanation:
The picutre shows optimal solution using moves described by the vectors: [0, 2], [3, 1] and [2, -2]. Other optimal soultion is: [0, 2], [-3, 1] and [-2, -2]. The movments order matters.
n ≤ 200000
----------------------------------------------------------------------------------------------------
My idea was to sort 4 times by the first coordinate and by the second and then check to maximum positive or negative sum. It doesn't give the correct answers. Here are the tests and the code:
#include <iostream> #include <algorithm> using namespace std; const int MAX = 200001; using II = pair<int, int>; II tab_X1[MAX]; // sorted by X II tab_Y1[MAX]; // sorted by Y II tab_X2[MAX]; // sorted by X II tab_Y2[MAX]; // sorted by Y long long maximum = 0; bool sort_X1(const II & v1, const II & v2) { if (v1.first < v2.first) return true; else if (v1.first == v2.first && v1.second < v2.second) return true; return false; } bool sort_Y1(const II & v1, const II & v2) { if (v1.second < v2.second) return true; else if (v1.second == v2.second && v1.first < v2.first) return true; return false; } bool sort_X2(const II & v1, const II & v2) { if (v1.first < v2.first) return true; else if (v1.first == v2.first && v1.second > v2.second) return true; return false; } bool sort_Y2(const II & v1, const II & v2) { if (v1.second < v2.second) return true; else if (v1.second == v2.second && v1.first > v2.first) return true; return false; } long long sum(long long x, long long y) { return x*x + y*y; } void max_SUM(const II (&tab)[MAX], int n) { long long x = 0, y = 0; for (int i = 0; i < n; ++i) { x += tab[i].first; y += tab[i].second; maximum = max(maximum, sum(x, y)); } x = y = 0; for (int i = n - 1; i > - 1; --i) { x += tab[i].first; y += tab[i].second; maximum = max(maximum, sum(x, y)); } } int main() { std::ios_base::sync_with_stdio(0); int n; cin >> n; int x, y; for (int i = 0; i < n; ++i) { cin >> x >> y; tab_X1[i].first = tab_X2[i].first = tab_Y1[i].first = tab_Y2[i].first = x; tab_X1[i].second = tab_X2[i].second = tab_Y1[i].second = tab_Y2[i].second = y; } sort(tab_X1, tab_X1 + n, sort_X1); sort(tab_X2, tab_X2 + n, sort_X2); sort(tab_Y1, tab_Y1 + n, sort_Y1); sort(tab_Y2, tab_Y2 + n, sort_Y2); max_SUM(tab_X1, n); max_SUM(tab_X2, n); max_SUM(tab_Y1, n); max_SUM(tab_Y2, n); cout << maximum << '\n'; }
Could you help me to write a faster algorithm again? The first one topic haven't been clear and sorry for it, but this one is really clear. Counting on you. I take to heart every advice. Thanks and reagards

This post has been edited by Vaxler: 11 November 2017 - 03:14 PM