8637. Sort the points

 

Given the coordinates of n points on a plane, print them in ascending order of the sum of their coordinates. If the sums of the coordinates are equal, the points should be sorted in ascending order of the x-coordinate.

 

Input. Each line contains a pair of numbers x, y (0 ≤ x, y ≤ 109) representing the coordinates of a single point.

 

Output. Print the coordinates of the points in ascending order of the sum of their coordinates. Each point’s coordinates should be printed on a separate line.

 

Sample input

Sample output

3 4

1 2

5 1

3 3

2 1

1 2

2 1

3 3

5 1

3 4

 

 

SOLUTION

sort

 

Algorithm analysis

Define a structure Point that contains the x-coordinate and y-coordinate of a point. Implement a comparator according to the problem statement, sort the points, and print them.

 

Algorithm implementation

Define a structure Point representing a point.

 

struct Point

{

public:

  int x, y;

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

};

 

Declare a vector of points.

 

vector<Point> p;

 

The function f is a comparator. Points are sorted in ascending order of the sum of their coordinates. If the sums of the coordinates are equal, the points are sorted in ascending order of the x-coordinate.

 

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;

}

 

The main part of the program. Read the input data.

 

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

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

 

Sort the points.

 

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

 

Print the points.

 

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

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

 

Algorithm implementation – SET with comparator

 

#include <cstdio>

#include <set>

using namespace std;

 

int i, x, y;

 

struct Point

{

public:

  int x, y;

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

};

 

int operator< (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;

}

 

multiset<Point> p;

multiset<Point>::iterator iter;

 

int main(void)

{

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

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

 

  for (iter = p.begin(); iter != p.end(); iter++)

    printf("%d %d\n", (*iter).x, (*iter).y);

 

  return 0;

}

 

Algorithm implementation – 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;

}

 

Algorithm implementation – 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;

}

 

Algorithm implementation – 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 implementation

 

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();

  }

}

 

Python implementation

 

import sys

 

Represent a point as a pair (x, y). The list p will contain all the input points.

 

p = []

 

Read the input points. Store them in the list p.

 

for line in sys.stdin:

  x, y = map(int, line.split())

  p.append((x, y))

 

Sort the points according to the given criterion.

 

p.sort(key = lambda point: (point[0] + point[1], point[0]))

 

Print the answer.

 

for x, y in p:

  print(x, y)

 

Python implementation – class + comparator

 

import sys

 

Define the Point class.

 

class Point:

  def __init__(self, x, y):

    self.x = x

    self.y = y

 

Define the comparator f to compare two points.

 

def f(a, b):

  if a.x + a.y == b.x + b.y:

    return a.x < b.x

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

 

The list p will contain all the input points.

 

p = []

 

Read the input points. Store them in the list p.

 

for line in sys.stdin:

  x, y = map(int, line.split())

  p.append(Point(x, y))

 

Sort the points according to the given criterion.

 

p.sort(key = lambda point: (point.x + point.y, point.x))

 

Print the answer.

 

for point in p:

  print(point.x, point.y)