import java.util.Arrays;
public class SortingPoints {
public static class Point {
int x;
int y;
public Point(int x, int y)
{
this.x = x;
this.y = y;
}
@Override
public String toString()
{
return "(" + x + ", " + y + ")";
}
}
private static int direction(
Point pi, Point pj, Point pk)
{
return (pk.x - pi.x) * (pj.y - pi.y)
- (pj.x - pi.x) * (pk.y - pi.y);
}
private static int compare(
Point pi, Point pj, Point pk)
{
if (pk.y - pi.y >= 0 && pj.y - pi.y < 0)
return 1;
if (pk.y - pi.y < 0 && pj.y - pi.y >= 0)
return -1;
if (direction(pi, pj, pk) == 0) {
if (pk.x - pi.x == 0 && pj.x - pi.x == 0) {
if (Math.abs(pk.y - pi.y)
> Math.abs(pj.y - pi.y))
return -1;
else
return 1;
}
if (pk.x - pi.x > 0
&& pj.x - pi.x < 0)
return 1;
else if (pk.x - pi.x < 0
&& pj.x - pi.x > 0)
return -1;
else if (Math.abs(pk.x - pi.x)
> Math.abs(pj.x - pi.x))
return -1;
else
return 1;
}
if (direction(pi, pj, pk) > 0)
return 1;
else
return -1;
}
private static void merge(
Point[] points,
int p, int q,
int r, Point p0)
{
int n1 = q - p + 1;
int n2 = r - q;
Point[] L = new Point[n1];
Point[] R = new Point[n2];
for (int i = 0; i < n1; i++)
L[i] = points[p + i];
for (int j = 0; j < n2; j++)
R[j] = points[q + 1 + j];
int i = 0, j = 0;
for (int k = p; k <= r; k++) {
if (i == n1)
points[k] = R[j++];
else if (j == n2)
points[k] = L[i++];
else if (compare(p0, L[i], R[j]) < 0)
points[k] = L[i++];
else
points[k] = R[j++];
}
}
public static void mergeSort(
Point[] points, int p,
int r, Point p0)
{
int q;
if (p < r) {
q = (p + r) / 2;
mergeSort(points, p, q, p0);
mergeSort(points, q + 1, r, p0);
merge(points, p, q, r, p0);
}
}
public static void main(String[] args)
{
Point O = new Point(0, 0);
Point[] points
= { new Point(1, 0),
new Point(0, -1),
new Point(-1, 0),
new Point(0, 1) };
System.out.println(
"Points: "
+ Arrays.toString(points));
System.out.println();
mergeSort(points, 0, 3, O);
System.out.println(
"After sorting with"
+ " reference point " + O);
System.out.println(
Arrays.toString(points));
System.out.println();
O = new Point(1, 1);
mergeSort(points, 0, 3, O);
System.out.println(
"After sorting with"
+ " reference point " + O);
System.out.println(
Arrays.toString(points));
System.out.println();
points = new Point[] {
new Point(-98, -65),
new Point(-65, -60),
new Point(65, -52),
new Point(-10, -47),
new Point(-7, -46),
new Point(26, -89),
new Point(72, -26),
new Point(66, -52),
new Point(69, 73),
new Point(-64, 0)
};
O = new Point(0, 0);
System.out.println(
"Points: "
+ Arrays.toString(points));
System.out.println();
mergeSort(points, 0, 9, O);
System.out.println(
"After sorting with"
+ " reference point " + O);
System.out.println(
Arrays.toString(points));
}
}