A could do the simple solution there I have 4 points of square and simple calculations of dist to this square. But i found this very easy and i figure out difficult formula for equations of the lines which bounding this square. I calculates dist for this lines and analyzing them.

This is initialization of square:
/*
void init(Point p1, Point p2){
    int64_t dx = p1.x-p2.x, dy = p1.y-p2.y;
    a = dx + dy; // some coof for line-equation
    b = dx - dy;
    c1 = dx*(p1.x-p1.y) + dy*(p1.x+p1.y);
    c2 = dy*(p2.x-p2.y) - dx*(p2.x+p2.y);
    dc = dx*dx + dy*dy; // delta between c-coof two parallel lines
    if (dc == 0) {
        // if square is dot
        c1 = p1.x;
        c2 = p1.y;
   }
}
*/
There i calculate dists to lines
/*
if (dc == 0){
    return std::hypot((p0.x - c1), (p0.y - c2));
} else {
    double
    d1 = (b*(p0.y) - a*(p0.x) + c1)/sqrt(2*dc), // signed dist to first line
    d2 = (b*(p0.x) + a*(p0.y) + c2)/sqrt(2*dc), // signed dist to perpendicular to first line
    d = sqrt(dc/2.0); // delta between two parallel lines (a side of square)
......
*/
"d" always is positive (if square isn't dot), bcs "(d1 - d) < d1" (dist to nearest line less than dist to farthest line)



there is some conditionals for calculate the dist to square
/*
if (d1 < 0) {
    if (d2 < 0) {
        // 1 corner   x1 = (c1*a - c2*b)/(2.0*dc), y1 = (-c1*b - c2*a)/(2.0*dc)
    } else if(d2 <= d){
        // 1 side
        return fabs(d1);
    } else {
        // 2 corner   x2 = (c1*a - c2*b)/(2.0*dc) + (b/2.0), y2 = (-c1*b - c2*a)/(2.0*dc) + (a/2.0)
    }
} else if (d1 <= d) {
    if (d2 < 0){
        // 2 side
        return fabs(d2);
    } else if(d2 <= d){
        // inside square
        return 0;
    } else {
        // 3 side
        return fabs(d2 - d);
    }
} else {
    if (d2 < 0){
        // 3 corner   x3 = (c1*a - c2*b)/(2.0*dc) - (a/2.0), y3 = (-c1*b - c2*a)/(2.0*dc) + (b/2.0)
    } else if(d2 <= d){
        // 4 side
        return fabs(d1 - d);
    } else {
        // 4 corner   x4 = (c1*a-c2*b)/(2.0*dc) + (b-a)/2.0, y4 = (p0.y + (c1*b+c2*a)/(2.0*dc) + (a+b)/2.0
    }
}
*/
after this we sorting dist with num, and print the answer

tests:
8
0 0 2 2
2 4 0 6
-8 -3 -8 -7
7 11 4 15
5 -5 9 -6
-2 -2 -2 -4
-4 6 -8 10
6 6 10 6
.....
6 2 : ans is "8 1 2 5 6 4 7 3"
0 0 : ans is "1 6 2 5 7 3 8 4"

Edited by author 26.08.2020 02:41

I got acc but for test case "0 0"
it's not "1 6 2 5 7 3 8 4"
and i got "1 8 6 2 5 7 3 4"