8637. Сортировка точек

Заданы координаты n точек на плоскости. Вывести их в порядке возрастания сумм координат. В случае равной суммы координат точки следует отсортировать по возрастанию абсциссы.

Вход. Каждая строка содержит пару чисел x, y (0 ≤ x, y ≤ 10⁹) – координаты точки.

Выход. Вывести координаты точек в порядке возрастания сумм координат. Координаты каждой точки выводить в отдельной строке.

Пример входа	Пример выхода
3 4 1 2 5 1 3 3 2 1	1 2 2 1 3 3 5 1 3 4

РЕШЕНИЕ

сортировка

Анализ алгоритма

Объявим структуру Point, содержащую абсциссу x и ординату y точки. Реализуем компаратор согласно условию задачи. Отсортируем и выведем точки.

Реализация алгоритма

Объявим структуру точка – Point.

struct Point

{

public:

int x, y;

Point(int x, int y) : x(x), y(y) {}

};

Объявим вектор точек.

vector<Point> p;

Функция f является компаратором. Точки сортируем в порядке возрастания сумм координат. В случае равной суммы координат точки сортируем по возрастанию абсциссы.

int f(Point a, Point b)

{

if (a.x + a.y == b.x + b.y) return a.x < b.x;

return a.x + a.y < b.x + b.y;

}

Основная часть программы. Читаем входные точки.

while (scanf("%d %d", &x, &y) == 2)

p.push_back(Point(x, y));

Сортируем точки.

sort(p.begin(), p.end(), f);

Выводим отсортированные точки.

for (i = 0; i < p.size(); i++)

printf("%d %d\n", p[i].x, p[i].y);

Реализация алгоритма – Heap Sort

#include <cstdio>

#include <vector>

using namespace std;

int a, b, i, n;

struct Point

{

public:

int x, y;

Point(int x, int y) : x(x), y(y) {}

};

vector<Point> m;

int f(Point a, Point b)

{

if (a.x + a.y == b.x + b.y) return a.x < b.x;

return a.x + a.y < b.x + b.y;

}

int left(int i)

{

return 2 * i;

}

int right(int i)

{

return 2 * i + 1;

}

void swap(int &i, int &j)

{

int temp = i; i = j; j = temp;

}

// max - heap

void heapify(vector<Point> &a, int i, int n, int f(Point a, Point b))

{

int largest = 0;

int l = left(i);

int r = right(i);

if (l <= n && f(a[i], a[l])) largest = l;

else largest = i;

if (r <= n && f(a[largest], a[r])) largest = r;

if (largest != i)

{

swap(a[i], a[largest]);

heapify(a, largest, n, f);

}

}

void BuildHeap(vector<Point> &a, int n, int f(Point a, Point b))

{

for (int i = n / 2; i > 0; i--)

heapify(a, i, n, f);

}

void HeapSort(vector<Point> &a, int n, int f(Point a, Point b))

{

BuildHeap(a, n, f);

for (int i = n; i >= 2; i--)

{

swap(a[1], a[i]);

heapify(a, 1, i - 1, f);

}

}

int main(void)

{

m.push_back(Point(0, 0));

while (scanf("%d %d", &a, &b) == 2)

m.push_back(Point(a, b));

HeapSort(m, m.size() - 1, f);

for (i = 1; i < m.size(); i++)

printf("%d %d\n", m[i].x, m[i].y);

return 0;

}

Реализация алгоритма – Merge Sort

#include <cstdio>

#include <vector>

#include <algorithm>

using namespace std;

int i, n, a, b;

struct Point

{

public:

int x, y;

Point() {}

Point(int x, int y) : x(x), y(y) {}

};

vector<Point> lst;

int f(Point a, Point b)

{

if (a.x + a.y == b.x + b.y) return a.x < b.x;

return a.x + a.y < b.x + b.y;

}

void merge(vector<Point> &a, int bleft, int bright, int cleft, int cright)

{

// a[bleft..bright] and a[cleft..cright] are merged into a[bleft..cright]

int i, left = bleft, len = cright - bleft + 1;

Point *res = new Point[len];

for (i = 0; i < len; i++)

{

if ((bleft > bright) || (cleft > cright)) break;

if (f(a[bleft], a[cleft])) res[i] = a[bleft], bleft++;

else res[i] = a[cleft], cleft++;

}

while (bleft <= bright) res[i++] = a[bleft++];

while (cleft <= cright) res[i++] = a[cleft++];

for (i = left; i < left + len; i++) a[i] = res[i - left];

delete[] res;

}

void mergeSort(vector<Point> &a, int left, int right)

{

if (left >= right) return;

int middle = (left + right) / 2;

mergeSort(a, left, middle);

mergeSort(a, middle + 1, right);

merge(a, left, middle, middle + 1, right);

}

int main(void)

{

while (scanf("%d %d", &a, &b) == 2)

lst.push_back(Point(a, b));

mergeSort(lst, 0, lst.size() - 1);

for (i = 0; i < lst.size(); i++)

printf("%d %d\n", lst[i].x, lst[i].y);

return 0;

}

Реализация алгоритма – Quick Sort

#include <cstdio>

#include <vector>

using namespace std;

int i, n, a, b;

struct Point

{

public:

int x, y;

Point(int x, int y) : x(x), y(y) {}

};

vector<Point> lst;

int f(Point a, Point b)

{

if (a.x + a.y == b.x + b.y) return a.x < b.x;

return a.x + a.y < b.x + b.y;

}

void swap(Point &i, Point &j)

{

Point temp = i; i = j; j = temp;

}

int Partition(vector<Point> &m, int L, int R)

{

Point x = m[L];

int i = L - 1, j = R + 1;

while (1)

{

do j--; while (f(x, m[j]));

do i++; while (f(m[i], x));

if (i < j) swap(m[i], m[j]); else return j;

}

}

void QuickSort(vector<Point> &m, int L, int R)

{

if (L < R)

{

int q = Partition(m, L, R);

QuickSort(m, L, q); QuickSort(m, q + 1, R);

}

}

int main(void)

{

while (scanf("%d %d", &a, &b) == 2)

lst.push_back(Point(a, b));

QuickSort(lst, 0, lst.size() - 1);

for (i = 0; i < lst.size(); i++)

printf("%d %d\n", lst[i].x, lst[i].y);

return 0;

}

Java реализация

import java.util.*;

class Point

{

int x, y;

public Point(int x, int y)

{

this.x = x;

this.y = y;

}

}

public class Main

{

public static class MyFun implements Comparator<Point>

{

public int compare(Point a, Point b)

{

if (a.x + a.y == b.x + b.y) return a.x - b.x;

return a.x + a.y - b.x - b.y;

}

}

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

Vector<Point> p = new Vector<Point>();

while(con.hasNext())

{

int x = con.nextInt();

int y = con.nextInt();

p.add(new Point(x,y));

}

Collections.sort(p, new MyFun());

for(int i = 0; i < p.size(); i++)

System.out.println(p.get(i).x + " " + p.get(i).y);

con.close();

}

}