Nöqtələrin sıralanması#8637

Nöqtələrin sıralanması (Həll təhlili)

Point strukturu elan edək, hansı ki, nöqtənin $x$ absisi və $y$ ordinatını ehtiva edir. Problemin şərtinə uyğun olaraq müqayisə edici funksiyanı reallaşdıraq. Nöqtələri sırala və çıxışa ver.

Alqoritmin həyata keçirilməsi

Point strukturu nöqtəni təqdim edir.

struct Point
{
public:
  int x, y;
  Point(int x, int y) : x(x), y(y) {}
};

Nöqtələrdən ibarət vektor elan edək.

vector<Point> p;

f funksiyası müqayisə edici funksiyadır. Nöqtələr koordinatları cəmlərinin artma ardıcıllığına görə sırala. Koordinatların cəmi bərabər olduğu halda, nöqtələr absisinin artma ardıcıllığına görə sırala.

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

Proqramın əsas hissəsi. Giriş nöqtələrini oxu.

while (scanf("%d %d", &x, &y) == 2)
  p.push_back(Point(x, y));

Nöqtələri sırala.

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

Sıralanmış nöqtələri çıxışa ver.

for (i = 0; i < p.size(); i++)
  printf("%d %d\n", p[i].x, p[i].y);

Java reallaşması

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 reallaşması

import sys

Nöqtə $(x, y)$ cütü şəklində təqdim olunacaq. $p$ siyahısı bütün giriş nöqtələrini ehtiva edəcək.

p = []

Giriş nöqtələrini oxu. Onları $p$ siyahısına əlavə et.

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

Nöqtələri verilmiş meyara görə sırala.

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

Cavabı çıxışa ver.

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

Python reallaşması — sinif + müqayisəçi

import sys

Point sinifini elan edək.

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

İki nöqtənin müqayisəsi üçün f müqayisəçisini elan edək.

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$ siyahısı bütün giriş nöqtələrini ehtiva edəcək.

p = []

Giriş nöqtələrini oxu. Onları $p$ siyahısına əlavə et.

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

Nöqtələri verilmiş meyara görə sırala.

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

Cavabı çıxışa ver.

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