Сортування точок#8637

Сортування точок (Розбір)

Оголосимо структуру 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);

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

Java

Python реалізація

import sys

Точку представлятимемо у вигляді пари $(x, y)$ . Список $p$ міститиме всі вхідні точки.

p = []

Читаємо вхідні точки. Заносимо їх у список $p$ .

for line in sys.stdin:
  x, y = map(int, line.split())
  p.append((x, y))

Сортуємо точки згідно заданого критерію.

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

Виводимо відповідь.

for x, y in p:
  print(x, y)

Python реалізація — клас + компаратор

import sys

Оголосимо клас Point

class Point:
  def __init__(self, x, y):
    self.x = x
    self.y = y

Оголосимо компаратор f для порівняння двох точок.

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

Список $p$ міститиме всі вхідні точки.

p = []

Читаємо вхідні точки. Заносимо їх у список $p$ .

for line in sys.stdin:
  x, y = map(int, line.split())
  p.append(Point(x, y))

Сортуємо точки згідно заданого критерію.

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

Виводимо відповідь.

for point in p:
  print(point.x, point.y)