2016-03-03 06:25

# 凸包问题，但是不知道哪里出错了

#include
#include
#include
#include
using namespace std;
#define MaxNode 1000
int stack[MaxNode];
int top;
struct POINT
{
int x;
int y;
};
struct POINT point[MaxNode];
void swap(struct POINT point[], int m, int n){//点之间的数据交换
struct POINT temp;
temp = point[m];
point[m] = point[n];
point[n] = temp;

}
double multi(struct POINT p1, struct POINT p2, struct POINT p0){//叉乘,p1点是转折点
return (p2.x - p1.x)*(p0.y - p1.y) - (p2.y - p1.y)*(p0.x - p1.x);
}
double distance(struct POINT p1, struct POINT p2){//两点之间的距离
return((p1.x - p2.x) ^ 2 + (p1.y - p2.y) ^ 2) ^ (1 / 2);
}
int cmp(const void *a, const void *b)
{
struct POINT *c = (struct POINT *)a;
struct POINT *d = (struct POINT *)b;
double k = multi(*c, *d, point[0]);
if (k else if (k == 0 && distance(*c, point[0]) >= distance(*d, point[0])) return 1; //极角相同，比距离
else return -1;
}
double jijiao(POINT p1, POINT p0){
return(p1.y - p0.y) / (p1.x - p0.x);
}
void gscan(int n){
for (int i = 0; i < n; i++){//找到P0基础点
int u = 0;
if ((point[i].y < point[u].y) || (point[i].y == point[u].y&&point[i].x < point[u].x))
u = i;
swap(point, 0, u);
}
qsort(point + 1, n - 1, sizeof(point[0]), cmp);//将剩余的点以极角由小到大排序
for (int r = 0; r < 3; r++)
stack[r] = r;
top = 2;
for (int k = 3; k < n; k++){
while (multi(point[top], point[k], point[top - 1]) >0){
if (top == 0)break;
top--;
}
top++;
stack[top] = k;
}
}
int main(){
int n;
cin >> n;
struct POINT point;
for (int i = 0; i < 3; i++){
cin >> &point[i].x >> &point[i].y;
}
gscan(n);
for (int w = 0; w < n; w++){
cout << stack[w] << endl;
}
}

• 点赞
• 写回答
• 关注问题
• 收藏
• 邀请回答