尋找最遠點對（凸包求解），

題目來源：https://biancheng.love/contest/41/problem/B/index

尋找最遠點對

題目描述

TD走廊裡有一關“勇闖梅花樁”，水面上稀稀落落地立著幾根柱子。Nova君自認為輕功不錯，覺得可以在任意兩根柱子之間跳躍，現在他想挑戰一次跨越距離最遠的兩根柱子。請問，最遠距離是多少？（由於木樁以橫縱坐標形式給出，為了計算方便，避免求平方根，答案只需給出距離的平方即可）

輸入

多組測試數據（組數不超過10），對於每組數據，第一行為一個正整數N，代表梅花樁的個數，接下來N行，每行兩個正整數xi， yi分別代表第 i 根樁子的橫縱坐標。 （數據在INT范圍內）

輸出

對於每組數據，輸出一行，為距離最遠的兩根柱子的距離的平方。

輸入樣例

3
1 1
1 2
0 0

輸出樣例

5

解題思路：
求出最遠的點對，可以化為求出對應的凸包上最遠的兩個點。

平面凸包 ：

 定義： 對一個簡單多邊形來說，如果給定其邊界上或內部的任意兩個點，連接這兩個點的線段上的所有點都被包含在該多邊形的邊界上或內部的話，則該多邊形為凸多邊形 。

在解決平面凸包下面介紹了兩種算法：

一、  Graham掃描法，運行時間為O(nlgn)。

二、  Jarvis步進法，運行時間為O(nh),h為凸包中的頂點數。

推薦博客：http://blog.csdn.net/bone_ace/article/details/46239187
推薦博客：http://www.cnblogs.com/jbelial/archive/2011/08/05/2128625.html
給出代碼：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #define INF -110
 5 
 6 using namespace std;
 7 long long i,j,k,n,top,ans;
 8 
 9 struct Node
10 {
11  int x;
12  int y;
13 }no[1000010],stack[1000010];
14 
15 long long dis(Node p1,Node p2)
16 {
17     return (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y);
18 }
19 
20 long long mult(Node p1,Node p2,Node p0)
21 {
22     return ((p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y));
23 }
24 
25 long long cmp(Node a,Node b)
26 {
27     if(mult(a,b,no[0])>0)
28         return 1;
29     else if(mult(a,b,no[0])==0&&dis(a,no[0])<dis(b,no[0]))
30         return 1;
31     return 0;
32 }
33 
34 void work()
35 {
36     k=0;
37     for(i=1; i<n; i++)
38     {
39         if(no[k].y>no[i].y || ((no[k].y == no[i].y) && no[k].x > no[i].x))
40             k = i;
41     }
42     Node tmp;
43     tmp = no[0];
44     no[0] = no[k];
45     no[k] = tmp;
46     sort(no+1,no+n,cmp);
47     top = 2;
48     stack[0] = no[0];
49     stack[1] = no[1];
50     stack[2] = no[2];
51     for(i=3; i<n; i++)
52     {
53         while(top>1 && mult(no[i],stack[top],stack[top-1])>=0)
54             top--;
55         stack[++top] = no[i];
56     }
57 }
58 
59 int main()
60 {
61     while(~scanf("%lld",&n))
62     {
63         for(i=0; i<n; i++)
64             scanf("%lld%lld",&no[i].x,&no[i].y);
65         work();
66         ans=INF;
67         for(i=0; i<=top; i++)
68         {
69             for(j=i+1; j<=top; j++)
70             {
71                 if(ans<dis(stack[i],stack[j]))
72                     ans=dis(stack[i],stack[j]);
73             }
74         }
75         printf("%lld\n",ans);
76     }
77     return 0;
78 }