Sort the points#8637

Sort the points (Editorial)

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

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

Java

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)