题目要求：
以最下最左点开始逆时针输出凸包。
若有多个点在同一坐标，只输出一个。
若凸包上有多个点在同一线上，只输出两端点。
算法思路：
跟着我的代码的注释一步一步画图应该挺容易理解的，主要还是运用了未知点与当前可能是凸包上的点的集合中的最后两个进行线位置比较这个方法来判断。
源代码：
//
// main.cpp
// ConvecHull
//
// Created by 胡昱 on 2021/11/1.
//
#include <iostream>
#include <algorithm>
using namespace std;
// 点类
class Point {
public:
int x;
int y;
Point(int X = 0, int Y = 0) {
x = X;
y = Y;
}
};
/* *********************** 全局变量定义 *********************** */
// 点数量
int n;
// 点集
Point* points;
/* *********************** 全局变量定义结束 *********************** */
// 根据最下最左原则进行点的比较
bool compareByXY(Point p1, Point p2) {
if(p1.y != p2.y) {
return p1.y < p2.y;
}
else {
return p1.x < p2.x;
}
}
// 计算斜率
double computeK(Point p1, Point p2) {
if(p1.x == p2.x) {
return __DBL_MAX__;
}
else {
return ((p1.y + 0.0) - (p2.y + 0.0)) / (p1.x - p2.x);
}
}
// 根据p1、p2与p的斜率进行点的比较，即判断l1是否在l2的顺时针方向（右）
bool compareByK(Point p, Point p1, Point p2) {
// 分别计算斜率
double k10 = computeK(p1, p);
double k20 = computeK(p2, p);
// 比较斜率
if(k10 == k20) {
return (abs(p1.x - p.x) + abs(p1.y - p.y)) > (abs(p2.x - p.x) + abs(p2.y - p.y));
}
else if(k10 >= 0 && k20 >=0) {
return k10 < k20;
}
else if(k10 >= 0 && k20 < 0){
return true;
}
else if(k10 < 0 && k20 >= 0) {
return false;
}
else {
return k10 < k20;
}
}
// 根据p1、p2与p0的斜率进行点的比较，即L10是否在L20的顺时针方向
bool compareByK0(Point p1, Point p2) {
return compareByK(points[0], p1, p2);
}
// 根据内（外）积来判断线的位置关系
bool compareByCrossProduct(Point p, Point p1, Point p2) {
if((p1.x - p.x) * (p2.y - p.y) - (p1.y - p.y) * (p2.x - p.x) > 0) {
return false;
}
else {
return true;
}
}
// 判断3个点是否同线
bool isLine(Point p1, Point p2, Point p3) {
return (computeK(p1, p2) == computeK(p1, p3));
}
// 凸包类
class ConvecHull {
public:
Point* points;
int maxN;
int index;
ConvecHull(int N = 100) {
points = new Point[N];
maxN = N;
index = -1;
}
~ConvecHull() {
delete [] points;
}
void push(Point p) {
points[++index] = p;
}
Point pop() {
return points[index--];
}
void println() {
for(int i = 0; i <= index; ++i) {
cout << points[i].x << " " << points[i].y <<endl;
}
}
void takeEndpoint() {
for(int i = 2; i <= index; ++i) {
if(isLine(points[i - 2], points[i - 1], points[i])) {
for(int j = i; j <= index; ++j) {
points[j - 1] = points[j];
}
--index;
}
}
}
};
// 主函数
int main(int argc, const char * argv[]) {
// 输入问题个数
int m;
cin >> m;
for(int c = 1; c <= m; ++c) {
// 输入点的数量
cin >> n;
// 创建点集
points = new Point[n];
// 输入点集并去除重复元素，因为若有多个点在同一坐标，只输出一个
for(int i = 0, x, y; i < n; ++i) {
cin >> x >> y;
Point temp = Point(x, y);
// 寻找是否有重复的元素
bool isFound = false;
for(int j = 0; j < i; ++j) {
if((temp.x == points[j].x) && (temp.y == points[j].y)) {
isFound = true;
break;
}
}
if(!isFound) {
points[i] = temp;
}
else {
--n;
--i;
}
}
// 寻找最下最左点p0，并将其放至数组第一位，即points[0]
sort(points, points + n, compareByXY);
// 对点集按照与p0的夹角大小进行从小到大（即逆时针）排序
sort(points + 1, points + n, compareByK0);
// 开始寻找凸包
// 初始化凸包
ConvecHull ch = ConvecHull(n);
ch.push(points[0]);
ch.push(points[1]);
ch.push(points[2]);
// 开始判断每个点是否可能是凸包上的点
Point p1, p2;
for(int i = 3; i < n; ++i) {
// 取栈顶与次栈顶元素，即当前凸包按逆时针方向的最后两个点
p1 = ch.pop();
p2 = ch.pop();
// 如果当前点pi与p1的连线在与p2的连线的右侧（逆时针方向夹角小于直角，即非左旋转）
// 则Li1这条线构成的凸包可以包含p2这个点
// 因此p2不是凸包上的点，且当前点pi可能是凸包上的点
// 随后不应该直接寻找新的点，而是应该拿pi与新的栈顶与次栈顶进行比较
if(!compareByCrossProduct(p2, points[i], p1)) {
ch.push(p2);
// 凸包内至少要保持3个元素
if(ch.index >= 2) {
--i;
}
else {
ch.push(points[i]);
}
}
else {
ch.push(p2);
ch.push(p1);
ch.push(points[i]);
}
}
// 删除凸包上在同一直线上的点，因为若凸包上有多个点在同一线上，只输出两端点
ch.takeEndpoint();
// 输出答案
cout << "case " << c << ":" << endl;
ch.println();
// 释放资源
delete [] points;
}
}
文章评论