凸包问题


写在前面,
以下算法的时间复杂度都为$O(nlogn)$

快包

讲解见教材《算法设计与分析基础》

#include<stdio.h>
#include<stdlib.h>

int g_result[240][2];

/*
*注:Pack[0][0]存放点的个数,pack[1]开始存放点的坐标。
*全局变量g_result[][]用来存放凸包上的点,即最终所要的答案。同样g_result[0][0]存放的是已找到的点的个数。
*/
void getResult(int Pack[240][2], int x1, int y1, int x2, int y2)
{
    // pack数组是用来存当前凸包的所有点的,resultpack数组是用来存当前凸包的上下包的点的
    int i,t,x3,y3,R,Rmax,tmax;
    int ResultPack[240][2];
    ResultPack[0][0] = 0;
    if(Pack[0][0] <= 2) return ;

    x3 = Pack[1][0];
    y3 = Pack[1][1];
    R = x1*y2 + x3*y1 + x2*y3 - x3*y2 - x2*y1 - x1*y3;
    Rmax = R;
    tmax = 1;
    for(i=1;i<=Pack[0][0];i++)
    {
        x3 = Pack[i][0];
        y3 = Pack[i][1];
        R = x1*y2 + x3*y1 + x2*y3 - x3*y2 - x2*y1 - x1*y3;//R的绝对值越大,那么x3这个点距离x1,x2所连成的线越远(叉积,教材) 
        if(R >= 0)
        {
            t = ++ResultPack[0][0];
            ResultPack[t][0] = x3;
            ResultPack[t][1] = y3;
        }
        if(R > Rmax)
        {
            Rmax = R;
            tmax = i;
        }
    }
    if(Rmax == 0)
    {
        for(i=1;i<=ResultPack[0][0];i++)
        {
            x3 = ResultPack[i][0];
            y3 = ResultPack[i][1];
            R = x1*y2 + x3*y1 + x2*y3 - x3*y2 - x2*y1 - x1*y3;
            if(R == 0 && !((x3==x2&&y3==y2)||(x3==x1&&y3==y1)))
            {
                t = ++g_result[0][0];
                g_result[t][0] = ResultPack[i][0];
                g_result[t][1] = ResultPack[i][1];
            }
        }
        return;
    }
    else
    {
        t = ++g_result[0][0];
        g_result[t][0] = Pack[tmax][0];
        g_result[t][1] = Pack[tmax][1];
    }
    getResult(ResultPack,x1,y1,Pack[tmax][0],Pack[tmax][1]);//新的上包递归
    getResult(ResultPack,Pack[tmax][0],Pack[tmax][1],x2,y2);//新的下包递归
}

int main()
{
    int Point[240][2];//Point存所有点。
    int i=1;
    int x1,y1,x2,y2,x3,y3;
    g_result[0][0]=0;Point[0][0]=0;//Point的第一行第一列元素存放包里面有几个点。初始化为0。
    printf("请输入所有点的坐标:\n");
    while(scanf("%d %d",&Point[i][0],&Point[i][1]) != EOF) i++;
    Point[0][0] = i-1;//前面i=1开始加的
    x1 = Point[1][0];
    y1 = Point[1][1];
    x2 = x1;
    y2 = y1;
    for(i=2;i<=Point[0][0];i++)
    {
        x3 = Point[i][0];
        y3 = Point[i][1];
        if(x3 < x1)//用枚举找最左边的点,用x1保存,最右边用x2保存
        {
            x1 = x3;
            y1 = y3;
        }
        else if(x3 > x2)
        {
            x2 = x3;
            y2 = y3;
        }
    }
    g_result[1][0] = x1;
    g_result[1][1] = y1;
    g_result[2][0] = x2;
    g_result[2][1] = y2;
    g_result[0][0] += 2;
    // 调转向量的方向,分别处理上下包
    getResult(Point, x1, y1, x2, y2);
    getResult(Point, x2, y2, x1, y1);

    printf("\n\n构成凸包的点有:\n");
    for(i=1;i<=g_result[0][0];i++)
        printf("(%d,%d)\n",g_result[i][0],g_result[i][1]);
    return 0;
}

Graham Scan

详细讲解

/*
两个向量逆时针夹角大于180,那么直观的可以看到是凹陷的
*/

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <iostream>

using namespace std;
#define MAXN 1002
int N;
struct Point
{
    double x,y;
    inline Point operator- (const Point &t)
    {
        Point ret;
        ret.x=x-t.x;
        ret.y=y-t.y;
        return ret;
    }
    inline Point operator+ (const Point &t)
    {
        Point ret;
        ret.x=x+t.x;
        ret.y=y+t.y;
        return ret;
    }
    inline int det(const Point &t)
    {
        return x*t.y-t.x*y;
    }
}d[MAXN];
bool cmpPoint(const Point &a, const Point &b)
{
    if (a.x!=b.x) return a.x<b.x;
    return a.y<b.y;
}
int convex[MAXN],cTotal;
void get_convex_hull()
{
    sort(d,d+N,cmpPoint);
    int Total=0,tmp;
    for (int i=0;i<N;++i)
    {
        while ( (Total>1) && 
                ((d[convex[Total-1]]-d[convex[Total-2]]).det(
                d[i]-d[convex[Total-1]])<=0) ) Total--;
        convex[Total++]=i;
    }
    tmp=Total;
    for (int i=N-2;i>=0;--i)
    {
        while ( (Total>tmp) &&
                ((d[convex[Total-1]]-d[convex[Total-2]]).det(
                d[i]-d[convex[Total-1]])<=0) ) Total--;
        convex[Total++]=i;
    }
    cTotal=Total;
}
int main()
{
    scanf("%d",&N);
    for (int i=0;i<N;++i) scanf("%lf%lf",&d[i].x,&d[i].y);
    get_convex_hull();
    double Ans=0;
    for (int i=0;i<cTotal-1;++i) cout << d[convex[i]].x << " " << d[convex[i]].y << endl;
    return 0;
}

/*
7
0 0
1 2
1 1
2 -1
3 2
3 -2
4 0
*/

凸包面积

先定最左边的那个点为s,然后将其余各点向s连一条线凸包分为多个三角形,通过叉积求出各个三角形的面积再求和。

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <iostream>

using namespace std;
#define MAXN 1002
int N;
double sx, sy;
struct Point
{
    double x,y;
    inline Point operator- (const Point &t)
    {
        Point ret;
        ret.x=x-t.x;
        ret.y=y-t.y;
        return ret;
    }
    inline Point operator+ (const Point &t)
    {
        Point ret;
        ret.x=x+t.x;
        ret.y=y+t.y;
        return ret;
    }
    inline int det(const Point &t)
    {
        return x*t.y-t.x*y;
    }
}d[MAXN];
bool cmpPoint(const Point &a, const Point &b)
{
    if (a.x!=b.x) return a.x<b.x;
    return a.y<b.y;
}
int convex[MAXN],cTotal;
void get_convex_hull()
{
    sort(d,d+N,cmpPoint);
    int Total=0,tmp;
    for (int i=0;i<N;++i)
    {
        while ( (Total>1) && 
                ((d[convex[Total-1]]-d[convex[Total-2]]).det(
                d[i]-d[convex[Total-1]])<=0) ) Total--;
        convex[Total++]=i;
    }
    tmp=Total;
    for (int i=N-2;i>=0;--i)
    {
        while ( (Total>tmp) &&
                ((d[convex[Total-1]]-d[convex[Total-2]]).det(
                d[i]-d[convex[Total-1]])<=0) ) Total--;
        convex[Total++]=i;
    }
    cTotal=Total;
}
double get_area(Point a, Point b)
{
    double area = 0;
    double x1 = a.x, y1 = a.y, x2 = b.x, y2 = b.y;
    area = fabs(((x2 - sx) * (y1 - sy) - (x1 - sx) * (y2 - sy)) / 2);
    return area;
}
int main()
{
    int T;
    cin >> T;

    while(T -- )
    {
        scanf("%d",&N);
        for (int i=0;i<N;++i) scanf("%lf%lf",&d[i].x,&d[i].y);
        get_convex_hull();
        double ans = 0;
        sx = d[0].x, sy = d[0].y;
        for(int i = 1 ; i <= cTotal ; i ++ )
        {
            ans += get_area(d[convex[i]], d[convex[i + 1]]);
        }

        printf("%.1lf\n", ans);        
    }

    return 0;
}

Author: Mrhh
Reprint policy: All articles in this blog are used except for special statements CC BY 4.0 reprint polocy. If reproduced, please indicate source Mrhh !
评论
 Previous
最近对问题 最近对问题
详解见教材《算法分析与设计基础》 板子#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <al
2020-11-21
Next 
Codeforces-1452B Toy Blocks Codeforces-1452B Toy Blocks
ProblemPortal Thoughts注意,题目说的是我们加入k个块之后,任意选取一堆的所有块来分,都能满足n-1堆数量相等。既然要任意一堆的话,也就是说最少相同的数量就是原序列中的最大值,同时还需要满足和是n-1的倍数。 Acc
  TOC