写了老长时间，主要是中间犯了很多小错，写的时候不够严谨啊。。。
写凸包算法时犯的一些错误
1.while(!is_left_turn(convex_next_top,convex_top,res_filter[i])){//attention ! …
当时忘了加这个！。。。
2.去除同线的点的时候，出错，光记得排除那些共线的点，反而忘了添加其他的不共线的普通点
3.排序时候，交换写错，下面的end应该是swap(points_set[j],points_set[i++]);
if(cmp(&points_set[j],&points_set[end]) < 0){
swap(points_set[end],points_set[i++]);
}
4.去除同线的点的时候，计算两点距离出错，两点间的距离公式竟然忘了求平方。。。
直接：(x1-x2)+(y1-y2)
5.忘了在while循环中，更新convex_next_top，convex_top
while(!is_left_turn(convex_next_top,convex_top,res_filter[i])){//attention !
convex.pop_back();
}
6.提交的时候忘了把#undef DEBUG加上
革命尚未成功啊。
#include <cstdio>
#include <cmath>
#include <vector>
using namespace std;
#define MAX_PNUM 1000
#define DEBUG 1
#undef DEBUG
namespace convex_hull{
using std::vector;
struct point{
int x;
int y;
}root;
//point points_list[MAX_PNUM];
int get_leftmost(point points_set[],int n){
int index = 0;
for(int j = 0; j < n ; j++){
if(points_set[j].x < points_set[index].x){
index = j;
}
else if(points_set[j].x == points_set[index].x){
if(points_set[j].y < points_set[index].y)
index = j;
}
}
return index;
}
void swap(point & a,point & b){
point c = a;
a = b;
b = c;
}
int distance_square(point a,point b){
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
void sort_by_angle(point points_set[],int begin,int end,int(*cmp)(void *,void *)){
if(begin >= end) return;
int i = begin;
for(int j = begin ; j < end ; j++){
if(cmp(&points_set[j],&points_set[end]) < 0){
swap(points_set[j],points_set[i++]);
}
}
swap(points_set[i],points_set[end]);
sort_by_angle(points_set,begin,i-1,cmp);
sort_by_angle(points_set,i+1,end,cmp);
}
int cmp(void * a,void * b){
point p1 = *(point *)a;
point p2 = *(point *)b;
return (p2.x-root.x)*(p1.y-root.y)-(p1.x-root.x)*(p2.y-root.y);
}
bool is_left_turn(point a,point b,point c){
return (c.x-a.x)*(b.y-a.y)-(b.x-a.x)*(c.y-a.y) < 0;
}
vector <point> graham_scan(point points_set[],int n){
vector <point> res_filter;
vector <point> convex;
int root_index = get_leftmost(points_set,n);
//delete the root from the set.n is the num of points
#ifdef DEBUG
printf("root-index:%d\n",root_index);
#endif
root = points_set[root_index];
points_set[root_index] = points_set[n-1];
n–;
//sort
sort_by_angle(points_set,0,n-1,cmp);
#ifdef DEBUG
printf("after sort:\n");
for(int i = 0 ; i < n ; i++)
printf("%d %d\n",points_set[i].x,points_set[i].y);
#endif
//delete the point with the same angle.
res_filter.push_back(points_set[0]);
for(int index = 1 ; index < n ; index++){
point temp = res_filter.back();
if(cmp(&points_set[index],&temp) == 0)
{
if(distance_square(points_set[index],root) > distance_square(temp,root)){
res_filter.pop_back();
res_filter.push_back(points_set[index]);
}
}
else
res_filter.push_back(points_set[index]);
}
#ifdef DEBUG
printf("after filter:\n");
for(int i = 0 ; i < res_filter.size() ; i++)
printf("%d %d\n",res_filter[i].x,res_filter[i].y);
#endif
//if all point is in one straight line,return null convex.
if(res_filter.size() <= 1) return convex;
//find convex hull
convex.push_back(root);
convex.push_back(res_filter[0]);
convex.push_back(res_filter[1]);
for(int i = 2 ; i < res_filter.size() ; i++){
point convex_top = convex.back();
point convex_next_top = convex[convex.size()-2];
while(!is_left_turn(convex_next_top,convex_top,res_filter[i])){//attention !
convex.pop_back();
convex_top = convex.back();
convex_next_top = convex[convex.size()-2];
}
convex.push_back(res_filter[i]);
}
#ifdef DEBUG
printf("convex:\n");
for(int i = 0 ; i < convex.size() ; i++)
printf("%d %d\n",convex[i].x,convex[i].y);
#endif
return convex;
}
}//end of namespace