郁闷啊郁闷，写了两个凸包的题目，都折戟在一两个NB数据上了。
tyvj上P1462的程序，赤果果的求凸包。自己写的Graham扫描法，极角顺序，从最下最右的点开始：
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#ifndef M_PI
#define M_PI 3.14159265358979323846
#endif
typedef struct {
double x, y, tg;
} coord;
// 算极角
inline double calc_tg (const coord b, const coord n)
{
double ret = atan2(n.y-b.y, n.x-b.x);
return ret >= 0 ? ret:ret+2*M_PI;
}
// 判断是否左转
#define tleft(a,b,c) \
(((b).x-(a).x)*((c).y-(a).y)-((c).x-(a).x)*((b).y-(a).y) <= 0.0)
// 快排之比较
int comp (const void *pa, const void *pb)
{
const coord *a = (const coord*)pa, *b = (const coord*)pb;
if (a->tg > b->tg)
return 1;
else if (a->tg != b->tg)
return -1;
else
return a->x > b->x ? 1:-1;
}
int main ()
{
int n, i, stktail;
coord *p, **stk, minc = {0.0, 1.0E22};
// 读入数据
scanf("%d", &n);
p = malloc(n*sizeof(coord));
stk = malloc(n*sizeof(coord*));
for (i=0; i<n; i++)
{
scanf("%lf %lf", &(p[i].x), &(p[i].y));
if ((p[i].y < minc.y) ||
((p[i].y == minc.y) && (p[i].x < minc.x)))
minc = p[i];
}
// 求凸包
for (i=0; i<n; i++)
p[i].tg = calc_tg(minc, p[i]);
qsort(p, n, sizeof(coord), comp);
stk[0] = p;
stk[1] = p+1;
stk[2] = p+2;
stktail = 2;
for (i=3; i<n; i++)
{
while (stktail >= 1)
{
coord *base = stk[stktail-1],
*last = stk[stktail];
if (tleft(*base, *last, p[i]))
stktail--;
else
break;
}
stk[++stktail] = p+i;
}
while (stk[stktail]->tg == stk[stktail-1]->tg)
stktail--;
// 按要求的顺序输出
int st = 0;
double minx = stk[0]->x;
for (i=stktail; i>=0; i--)
{
if (stk[i]->x < minx)
minx = stk[i]->x,
st = i;
else
break;
}
i = st;
do
{
printf("%.4lf %.4lf\n", stk[i]->x, stk[i]->y);
if (--i < 0)
i = stktail;
} while (i != st);
return 0;
}
运行结果：
#01: Accepted (0ms, 196KB)
#02: Accepted (0ms, 196KB)
#03: Accepted (0ms, 200KB)
#04: Accepted (0ms, 196KB)
#05: Accepted (0ms, 200KB)
#06: Accepted (0ms, 332KB)
#07: Accepted (293ms, 2936KB)
#08: Wrong Answer (637ms, 2936KB)
#09: Accepted (0ms, 224KB)
#10: Accepted (0ms, 304KB)
#11: Time Limit Exceeded (?, 2388KB)
错的那个可能是精度问题（但我尝试了，long double也过不去，所以也可能是写错了）。
最后一个超时。我已经各种优化了：把C++程序改成C，动态申请内存（不清0了），手动define内联函数，使用double而非long double…… 但还是超时。难道是qsort太慢了？
郁闷啊。可能我的实现比较烂，求神牛指导实现细节。
snack 发表于 Mon, 20 Jun 2011 23:03:28 +0000