UPC little C's King Canyon

First of all , The title is not clear , Is o n The farthest distance between two points .

I didn't write the code , Ask the coach for .

ps：gramham Algorithm video b standing

[ Computational geometry ]Graham Algorithm constructs convex hull （ Remanufacture ）_ Bili, Bili _bilibili

Title Description

Small C I especially like hitting primary school students “ Kingly pesticide ”, however , Today's little C But in the glory of the king, he was abused by the opposite side . as everyone knows , At present, the farthest distance of the king's glory attack is Huang Zhong , But small C Always playing with Huang Zhong being abused , Because he doesn't know when to turn it up . Small at this moment C Fighting with the opposite team in the middle , He thinks it is necessary for him to choose a suitable position to open , So that we can fight more enemy heroes . This is the time , Small C I also found a lot of soldiers and wild monsters nearby , He believes that these things can also increase experience , So we should also fight . Small C So I was thinking , If only I could hit everything in the whole King Canyon , But these things are always moving , And my own big move is not far enough , that , If I know the location of everything , My big trick is to hit everything , How far is the shortest ？ however , Small C Fantasy again , He wants to know the square of the shortest distance .

Input

Here you are. N, It means enemy hero 、 Soldier 、 The sum of wild monsters .
Next N That's ok , Two numbers per line , Represents a small C The location of the thing to hit .

Output

a line , It means small C Want to know the answer .

The sample input  Copy

4
0 0
0 1
1 1
1 0

Sample output  Copy

2

Tips

about 10% The data of ,N <= 100.
about 30% The data of ,N <= 1000.
about 100% The data of ,N <= 50000
Each coordinate is -10000 to 10000 Between the value of the

#include<bits/stdc++.h>
using namespace std;
#define REP(i, a, b) for ( int i = (a), _end_ = (b); i <= _end_; ++ i)
#define mem(a) memset ( (a), 0, sizeof (a))
#define str(a) strlen (a)
int n, top;
struct Node{
    int x;
    int y;
}node[60000], stack[60000];
int dist(Node p1, Node p2) {
    return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
}
int mult(Node p1, Node p2, Node p0) {
     return ((p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y));
}
int cmp(Node a, Node b) {
    if ( mult(a, b, node[0]) > 0)
        return 1;
    else if ( mult(a, b, node[0]) == 0 && dist(a, node[0]) < dist(b, node[0]))
        return 1;
    return 0;
}
void Gramham() {
    int k = 0 ;
    REP(i, 1, n - 1)
        if ( node[k].y > node[i].y || ((node[k].y == node[i].y) && node[k].x > node[i].x))
            k = i;
    Node tmp;
    tmp = node[0];
    node[0] = node[k];
    node[k] = tmp;//node[0] and node[k] swap 
    sort(node + 1, node + n, cmp);
    top = 2;
    stack[0] = node[0];
    stack[1] = node[1];
    stack[2] = node[2];
    REP(i, 3, n - 1) {
        while(top > 1 && mult(node[i], stack[top], stack[top - 1]) >= 0)
            top --;
        stack[++ top] = node[i];
    }
}
int main() {
    cin >> n;
    REP(i, 0, n - 1)
        cin >> node[i].x >> node[i].y;
    Gramham();
    int ans = -1;
    REP(i, 0, top)
        REP(j, i + 1, top)
            if ( ans < dist(stack[i], stack[j]))
                ans = dist(stack[i], stack[j]);
    cout << ans << endl;
    return 0;
}