凸包——五种解法

欢迎访问https://blog.csdn.net/lxt_Lucia&＃xff5e;&＃xff5e;

宇宙第一小仙女\(^o^)/&＃xff5e;&＃xff5e;萌量爆表求带飞&＃61;≡Σ((( つ^o^)つ~ dalao们点个关注呗&＃xff5e;&＃xff5e;

关于凸包&＃xff0c;之前一直漏掉了这一个&＃xff0c;上周末组队赛&＃xff0c;听说有一题就是凸包的模板&＃xff0c;可惜不会&＃xff0c;听说不算很难&＃xff0c;正好这周空余的课很少&＃xff0c;就顺便搞了8... 

目录

• 前言
• 解一&＃xff1a;穷举法&＃xff08;蛮力法&＃xff09;
• 解二&＃xff1a;分治法
• 解三&＃xff1a;Jarvis步进法
• 解四&＃xff1a;Graham扫描法
• 解五&＃xff1a;Melkman算法
• 快包算法代码&＃xff08;C语言&＃xff09;
• 例题&＃xff08; HDU 3285 &＃xff09;及模板

前言&＃xff1a;

首先&＃xff0c;什么是凸包&＃xff1f; 

1&＃xff09;可以形象地想成这样&＃xff1a;在地上放置一些不可移动的木桩&＃xff0c;用一根绳子把他们尽量紧地圈起来&＃xff0c;这就是凸包了。
2&＃xff09;假设平面上有p0~p12共13个点&＃xff0c;过某些点作一个多边形&＃xff0c;使这个多边形能把所有点都“包”起来。当这个多边形是凸多边形的时候&＃xff0c;我们就叫它“凸包”。如下图&＃xff1a; 

The vertices of a lattice polygon are in standard order if:
a) The first vertex is the one with the largest y value. If two vertices have the same y value, the one with the smaller x value is the first.
b) Vertices are given in clockwise order around the polygon. 

Write a program that reads a set of lattice points and outputs the vertices of the convex hull of the points in standard order.

Input

The first line of input contains a single integer P, (1 ≤ P ≤ 1000), which is the number of data sets that follow. The first line of each data set contains the data set number, followed by a space, followed by a decimal integer giving the number of points N, (3 ≤ N ≤ 50), in the set. The remaining lines in the data set contain the points in the set, at most 5 points per line (the last line may have fewer). Each point consists of 2 space separated decimal integer values representing the x and y coordinates
respectively.

Output

For each data set there are multiple lines of output. The first line contains a decimal integer giving the data set number followed by a single space, followed by a decimal integer giving the total number of vertices of the convex hull. The vertices of the convex hull follow, one per line in standard order. Each line contains the decimal integer x coordinate, a single space and the decimal integer y coordinate.

Sample Input

4
1 25
2 1 7 1 1 2 9 2 1 3
10 3 1 4 10 4 1 5 10 5
2 6 10 6 2 7 9 7 3 8
8 8 4 9 7 9 6 2 3 3
5 4 7 5 8 6 4 6 3 7
2 30
3 9 6 9 3 8 9 8 3 7
12 7 2 6 12 6 2 5 12 5
2 4 12 4 1 3 11 3 1 2
11 2 1 1 11 1 1 0 10 0
4 -1 10 -1 7 -2 10 -2 5 0
7 3 4 5 6 8 3 1 2 6
3 3
3 1 2 2 1 3
4 6
1 3 19 1 4 2 2 1 11 2
10 1
 

​​​​Sample Output

1 10

4 9

7 9

10 6

10 3

9 2

7 1

2 1

1 2

1 5

2 7

2 8

3 9

6 9

12 7

12 4

10 -2

7 -2

1 0

1 3

3 2

1 3

3 1

4 4

1 3

11 2

19 1

2 1

代码&＃xff1a;

#include

参考资料&＃xff1a;

https://blog.csdn.net/bone_ace/article/details/46239187

https://blog.csdn.net/foreverlin1204/article/details/6221986

https://blog.csdn.net/thewalker88/article/details/79504704