首页 > 代码库 > 【poj2187】最远点对（勉强凑数）

【poj2187】最远点对（勉强凑数）

2024-08-22 09:56:00   218人阅读

题目简述 

输入n个点，及其坐标，n<=50000，所有坐标都是不超过10000的整数组成，没有重点。

问最远点对间的距离的平方是多少

题解

这是一道旋转卡壳的裸题

我们要求这个多边形的直径，这可怎么办呢

首先，最远点对一定在凸包上，我们考虑这样一个凸包

显然的，卡在两个点上，一定可以转化成卡在一个边和一个点上

更显然的，如果卡在一条边上和一个点上，那么这个点一定离这个边最远

那么，这个点和这条边组成的三角形一定是包括这条边的三角形中最大的

再之，假定点i和点i+1卡到了点j

那么随着i增加，j也增加

根据这个单调性，我们可以计算出每条边对应的点了

那么直径也就等于边的端点到对应的点的距离

注意边界即可！

技术分享

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<string>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<queue>
#include<map>
#include<vector>
#include<set>
#define il inline
#define re register
using namespace std;
typedef double db;
const int N=100001;
struct P{int x,y;} a[N],s[N];
int n,top=0,ans=0;
il P operator-(P a,P b){
    return (P){a.x-b.x,a.y-b.y};
}
il int operator*(P a,P b){
    return a.x*b.y-a.y*b.x;
}
il int dis(P a){
    return a.x*a.x+a.y*a.y;
}
il bool cmp(P x,P y){
    if(abs((x-a[1])*(y-a[1]))>0) return (x-a[1])*(y-a[1])>0;
    return dis(x-a[1])<dis(y-a[1]);
}
il int S(P a,P b,P c){
    return abs((a-b)*(a-c))/2;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&a[i].x,&a[i].y);
    for(int i=2;i<=n;i++)
        if(a[i].y<a[1].y||(a[i].y==a[1].y&&a[i].x<a[1].x)) 
            swap(a[1],a[i]);
    sort(a+2,a+n+1,cmp);
    top=2;s[1]=a[1];s[2]=a[2];
    for(int i=3;i<=n;i++){
        while(top>1&&(a[i]-s[top-1])*(s[top]-s[top-1])>=0) top--;
        s[++top]=a[i];
    }
    for(int i=0;i<top;i++)
        s[i]=s[i+1];
    n=top;
    for(int i=0,j=2;i<n;i++){
        while(S(s[i],s[(i+1)%n],s[j])<S(s[i],s[(i+1)%n],s[(j+1)%n])) j=(j+1)%n;
        ans=max(dis(s[i]-s[j]),ans);
    }
    printf("%d",ans);
    return 0;
}

 

【poj2187】最远点对（勉强凑数）


联系
我们