TOJ 3589 likaer的最长点距

传送门：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

样例输出

思路：因为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
",ans);
    }
    return 0;
}

View Code