传送门：http://acm.tzc.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=3589
时间限制(普通/Jav a):7000MS/70000MS 内存限制:65536KByte
描述
我们都知道，炉子喜欢做题，尤其喜欢做likaer等牛出的神题。比如昨天炉子经过一天的奋斗，终于找到一个O(N ^ 2)的算法，成功水过了likaer牛出的最长点距（http://acm.tzc.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=3580）。
likaer牛深感压力很大――“这样的题都需要花一天……”，于是就给把N改成了50000，“接着做吧孩子。”
我们都知道炉子喜欢问问题――因为他什么都不会。所以炉子找到了你，一个强大的ACMer，来帮他解决这个问题。
输入
输入的第一行是样例数T，1 ≤ T ≤ 50。
每组样例第一行有一个整数N，是点的个数，1 ≤ N ≤ 50,000；
接下来有N行，每行两个整数Xi、Yi，是第i个点的X、Y坐标，-10,000 ≤ Xi ≤ 10,000，-10,000 ≤ Yi ≤ 10,000。
输出
每组样例输出一行，包含一个整数X，是最远的两个点的距离的平方（请注意不是距离而是距离的平方――这样可以避免使用double。）。
样例输入
1
3
0 0
1 1
2 2
样例输出
8
思路：因为n特别大，所以不能用暴力两个for循环遍历所有点找最远两个点。
考虑到最远点肯定在凸包上，所以转化为在先求凸包，再在凸包上循环2次暴力找最远点，这样就不会超时了
#include<iostream> #include<algorithm> #include<cstdio> #include<cstring> #include<string> #include<cstdlib> #include<cmath> #include<queue> #include<set> #include <sstream> #include <assert.h> #define LL long long using namespace std; int i,j,k,n,top,ans; struct note{int x,y; }p[50010],stack[50010]; int dis(note a,note b){return (a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y); } int mult(note p1,note p2,note p0){return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y); } int cmp(note a,note b){if(mult(a,b,p[0]) > 0){return 1;}else if(mult(a,b,p[0]) == 0 && (dis(a,p[0]) < dis(b,p[0]))){return 1;}return 0; } void solve(){k = 0;for(i = 1 ; i < n ; i++){if(p[k].y > p[i].y || (p[k].y == p[i].y) && p[k].x > p[i].x)k = i;}swap(p[0],p[k]);sort(p+1,p+n,cmp);top = 2;stack[0] = p[0];stack[1] = p[1];stack[2] = p[2];for(i = 3 ;i < n ; i++){while(top > 1 &&mult(p[i],stack[top],stack[top - 1]) >= 0)top--;stack[++top] = p[i];} } int main(){int t;for(scanf("%d",&t);t--;){scanf("%d",&n);for(i = 0 ; i < n ; i++){scanf("%d %d",&p[i].x,&p[i].y);}solve();ans = -1000;for(i = 0 ; i <= top ; i++){for(j = i+1 ;j <= top ; j++){if(ans < dis(stack[i],stack[j])){ans = dis(stack[i],stack[j]);}}}printf("%d\n",ans);}return 0; }
