凸包全解

Graham-Scan法序的选取1.

选取最低点中最左的一个作为参考点      
用叉乘来排序所有点的相对位置
时间复杂度
排序O(nlog n)
扫描O(n)
总的是O(nlog n)

Graham-Scan法的特殊情况
重复点
删除
共线点
对于不要求求共线点的情况，可以对叉乘做严格的判定。
对于要求求共线点的情况，没有办法简单而完美的处理：
A、B两点没有办法都加入凸包中

Graham-Scan法的另外一种序

用水平序
     先按y坐标排
     y相同的按x坐标排
2次扫描
     先从第1个点即0开始到最后1个点即9得到右链
     再从最后1个点即9开始到第1个点即0，不包括已经在右链的点

处理特殊情况
如果不要共线的点，则严格判断叉乘（即只有在左边才可以）
如果要共线的点，则叉乘等于0即共线也认为可以
直观的理解
很简洁，很完美~

代码一：

#include<math.h>
#include<stdio.h>
#include<algorithm>
using namespace std;
#define N 10005
#define PI 3.14159265
using namespace std;
struct point
{
    int x,y;
}p[N];
int dis(point p1,point p2)
{
    return ((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
int xmult(point p1,point p2,point p3)
{
    return (p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y);
}
bool cmp(point p1,point p2)
{
    int k=xmult(p[0],p1,p2);
    if(k>0||!k&&dis(p[0],p1)<dis(p[0],p2))
        return true;
    return false;
}
int Graham(point *p,int n)
{
    int x=p[0].x;
    int y=p[0].y;
    int mi=0;
    for(int i=0;i<n;i++)
    {
        if(p[i].y<y || p[i].y==y&&p[i].x<x)
        {
            x=p[i].x;
            y=p[i].y;
            mi=i;
        }
    }
    point tmp=p[0];
    p[0]=p[mi];
    p[mi]=tmp;//find down left

    sort(p+1,p+n,cmp);//sort

    int top=1;
    for(int i=2;i<n;i++)
    {
        while(xmult(p[top-1],p[top],p[i])<=0 &&top>=1)
        --top;
        p[++top]=p[i];
    }
    return top+1;//number of convex
}

View Code

#include<stdio.h> #include<algorithm> #include<fstream> #include<string.h> #include<iostream> using namespace std; const int MAX=550; struct point { int x; int y; int v; int i; int tmp; } Ini[MAX],res[MAX],p[MAX]; bool flag[MAX]; int ans[MAX]; bool cmp(point A,point B) { if(A.y==B.y)return A.x<B.x; return A.y<B.y; } bool cmp1(point A,point B) { if(A.v>B.v)return true; if(A.v==B.v) { if(A.x<B.x)return true; if(A.x==B.x&&A.y<B.y)return true; } return false; } int xmult(point A,point B,point C) { return (B.x-A.x)*(C.y-A.y)-(C.x-A.x)*(B.y-A.y); } int Graham(point *p,int n) { //if (n<3)return n; sort(p,p+n,cmp); memset(flag,false,sizeof(flag)); int i; int top=0; for(i=0; i<n; i++) { while(top>=2&&xmult(res[top-2],res[top-1],p[i])<0) { top--; } res[top++]=p[i]; res[top-1].tmp=i; } for(i=0;i<top;i++) flag[res[i].tmp]=true; int t=top+1; for(i=n-2; i>=0; i--) //i>=0 { while(top>=t&&xmult(res[top-2],res[top-1],p[i])<0) top--; if(!flag[i])res[top++]=p[i]; //if(i==0)top--; } /*for(i=0; i<top; i++) printf("$%d %d ",res[i].x,res[i].y);*/ return top; }

相关推荐