Poj 2187 旋转卡壳

Poj 2187 旋转卡壳求解

传送门

旋转卡壳，是利用凸包性质来求解凸包最长点对的线性算法，我们逐渐改变每一次方向，然后枚举出这个方向上的踵点对(最远点对),类似于用游标卡尺卡着凸包旋转一周，答案就在这其中的某个方向上。

直接暴力和旋转卡壳速度对比(仅此题)

#include <queue>

#include <cmath>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#define ll long long

#define inf 1000000000LL

#define mod 1000000007

using namespace std;

int read()

{

    int x=0,f=1;

    char ch=getchar();

    while(ch<'0'||ch>'9')

    {

        if(ch=='-')f=-1;

        ch=getchar();

    }

    while(ch>='0'&&ch<='9')

    {

        x=x*10+ch-'0';

        ch=getchar();

    }

    return x*f;

}

const int N = 5e4+10;

const double PI = acos(-1.0);

const double eps = 1e-12;

int dcmp(double x) {

    if(fabs(x)<eps) return 0; else return x<0? -1:1;

}

struct Pt {

    double x,y;

    Pt(double x=0,double y=0) :x(x),y(y) {};

};

typedef Pt vec;

vec operator - (Pt a,Pt b) { return vec(a.x-b.x,a.y-b.y); }

vec operator + (vec a,vec b) { return vec(a.x+b.x,a.y+b.y); }

bool operator == (Pt a,Pt b) {

    return dcmp(a.x-b.x)==0 && dcmp(a.y-b.y)==0;

}

bool operator < (const Pt& a,const Pt& b) {

    return a.x<b.x || (a.x==b.x && a.y<b.y);

}

vec rotate(vec a,double x) {

    return vec(a.x*cos(x)-a.y*sin(x),a.x*sin(x)+a.y*cos(x));

}

double cross(vec a,vec b) { return a.x*b.y-a.y*b.x; }

double dist(Pt a,Pt b) {

    //return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));

    return ((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));

}

vector<Pt> ConvexHull(vector<Pt> p) {

    sort(p.begin(),p.end());

    p.erase(unique(p.begin(),p.end()),p.end());

    int n=p.size() , m=0;

    vector<Pt> ch(n+1);

    for(int i=0;i<n;i++) {

        while(m>1 && cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--;

        ch[m++]=p[i];

    }

    int k=m;

    for(int i=n-2;i>=0;i--) {

        while(m>k && cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--;

        ch[m++]=p[i];

    }

    if(n>1) m--;

    ch.resize(m); return ch;

}

vector<Pt>q,con;

double RC(){

    con=ConvexHull(q);

    int n=con.size();

    if(n==2){         //处理特殊情况

        return dist(con[0],con[1]);

    }

    int i=0,j=0;

    for(int k=0;k<n;k++){

       if(!(con[i]<con[k])) i=k;

       if(con[j]<con[k]) j=k;

    }

    double res=0;

    int si=i,sj=j;

    while(i!=sj||j!=si){

        res=max(res,dist(con[i],con[j]));

        if(cross(con[(i+1)%n]-con[i],con[(j+1)%n]-con[j])<0){

            i=(i+1)%n;

        }else{

            j=(j+1)%n;

        }

    }

    return res;

}

int main(){

     int n=read();

     int x,y;

     for(int i=0;i<n;i++){

           x=read();y=read();

           q.push_back(Pt((double)x,(double)y));

     }

     printf("%.0f\n",RC());

     return 0;

}

巴特西

Poj 2187 旋转卡壳

Poj 2187 旋转卡壳求解

最新文章

热门文章