8637. Sort the
points
The coordinates of n
points are given on a plane. Print them in increasing order of sum of
coordinates. In the case of equal sum of point coordinates sort the points in
increasing order of abscissa.
Input. Each line contains the pair of numbers x, y (0 ≤ x, y ≤
109) – the coordinates of one point.
Output. Print the points
coordinates in ascending order of the sum of coordinates. Print the coordinates
of each point 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 |
sort
Declare a Point
structure containing the x abscissa and y ordinate of the point. Implement
the comparator according to the problem statement. Sort and print the points.
Declare the point structure Point.
struct Point
{
public:
int x, y;
Point(int x, int y) : x(x), y(y) {}
};
Declare the vector of
points.
vector<Point> p;
Function f
is a comparator. Sort the points in ascending order of sums of coordinates. If the points’ sum of coordinates are equal, sort them in ascending order of abscissa.
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 points.
while (scanf("%d %d", &x, &y) == 2)
p.push_back(Point(x, y));
Sort the points.
sort(p.begin(), p.end(), f);
Print the sorted
points.
for (i = 0; i < p.size(); i++)
printf("%d
%d\n", p[i].x, p[i].y);
Algorithm
realization – 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;
}
#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;
}
#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;
}
#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;
}
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();
}
}