题目大意： 个点，求出其凸包。如果有点在凸包的面或棱上，也要将其算进凸包中，将答案按字典序输出。
分析： 主要就是求解三维凸包，至于凸包面或棱上的点可以在求出凸包后再加进去。凸包上每个面都是三角形，如果在平面中就类似三角剖分一般。 增量法，主要算法流程就是： 初始化一个未退化的四面体； 如果新点在凸包内或凸包上，忽视掉； 如果新点在凸包外，删去它可以看到的面，并将其并入整个凸包中。 我们要对三点共线，四点共面的情况分别判断。 构成的法向量为能看到该面当且仅当，如果一个面都看不到，，那么说明该点在凸包内。 与凸包未被删去的轮廓相连，也就是那些只被删去过一次的边。 有图有真相：
AC code：
LL;typedef double DB;LD;;void open_init(){#ifndef ONLINE_JUDGEfreopen(“input.txt”, “r”, stdin);freopen(“output.txt”, “w”, stdout);#endif}void close_file(){#ifndef ONLINE_JUDGEfclose(stdin);fclose(stdout);#endif}const int MAXN = 109;int n;string input;string name[MAXN];string ansn[MAXN];int tot;struct pot{LL x, y, z;pot(LL x = 0, LL y = 0, LL z = 0):x(x),y(y),z(z){}friend pot operator + (const pot &a, const pot &b){return pot(a.x+b.x, a.y+b.y, a.z+b.z);}friend pot operator – (const pot &a, const pot &b){return pot(a.x-b.x, a.y-b.y, a.z-b.z);}friend LL operator * (const pot &a, const pot &b){return a.x*b.x+a.y*b.y+a.z*b.z;}friend pot operator ^ (const pot &a, const pot &b){return pot(a.y*b.z-a.z*b.y, a.z*b.x-a.x*b.z, a.x*b.y-a.y*b.x);}}v[MAXN];struct tri{int p[4];pot law;};tri s[MAXN*MAXN];int stot;set<int> valid, ans;int bel[MAXN][MAXN];bool del[MAXN*MAXN];queue<int> q;inline void read(int &pos, LL &x){int tmp = pos, i, f = 1;x = 0;while(input[pos] == ‘-‘ || isdigit(input[pos])) pos–;i = pos+1, pos–;if(input[i] == ‘-‘) f = -1;else x = input[i]-‘0’;while(isdigit(input[++i])) x = x*10+input[i]-‘0’;x *= f;}inline bool zero(const pot &a){return !a.x && !a.y && !a.z;}inline bool collinear(int a, int b, int c){return zero((v[a]-v[b])^(v[a]-v[c]));}inline bool coplanar(int a, int b, int c, int d){return ((v[b]-v[a])^(v[c]-v[a]))*(v[d]-v[a]) == 0;}inline void end(){cout << n << endl;sort(name+1, name+n+1);rep(i, 1, n)cout << name[i] << endl;exit(0);}pot law(int a, int b, int c){return (v[b]-v[a])^(v[c]-v[a]);}inline void add(int a, int b, int c){tri node;node.p[3] = node.p[0] = a, node.p[1] = b, node.p[2] = c;node.law = law(a, b, c);s[++stot] = node;valid.insert(stot);rep(i, 0, 2) bel[node.p[i]][node.p[i+1]] = stot;}inline void init(int a, int b, int c, int d){if(law(a, b, c)*(v[d]-v[a]) < 0) add(a, b, c);else add(a, c, b);}inline bool in(int a, int b, int c, int d){return ((v[b]-v[a])^(v[d]-v[a]))*((v[d]-v[a])^(v[c]-v[a])) >= 0;}inline bool in_tri(const tri &a, int b){int x(a.p[0]), y(a.p[1]), z(a.p[2]);if(!coplanar(a.p[0], a.p[1], a.p[2], b)) return false;return in(x, y, z, b) && in(y, z, x, b) && in(z, x, y, b);}int main(){open_init();scanf(“%d\n”, &n);rep(i, 1, n){char c;getline(cin, input);int j = input.size()-1;while((c=input[j]) == ‘\n’ || c == ‘\r’ || c == ‘ ‘)j–;read(j, v[i].z), read(j, v[i].y), read(j, v[i].x);name[i] = input.substr(0, j+1);}if(n == 1) end();int ch1 = 0;rep(i, 3, n)if(!collinear(1, 2, i)){ch1 = i;break;}if(!ch1) end();int ch2 = 0;rep(i, 3, n)if(i != ch1 && !coplanar(1, 2, ch1, i)){ch2 = i;break;}if(!ch2) end();init(1, 2, ch1, ch2), init(1, 2, ch2, ch1);init(2, ch1, ch2, 1), init(1, ch1, ch2, 2);set<int>::iterator it;rep(i, 3, n)if(i != ch1 && i != ch2){bool flag = false;for(it = valid.begin(); it != valid.end(); ++it)if(s[*it].law*(v[i]-v[s[*it].p[0]]) > 0){flag = true;q.push(*it);del[*it] = true;}if(!flag) continue;while(!q.empty()){int now = q.front();q.pop();valid.erase(now);rep(j, 0, 2)if(!del[bel[s[now].p[j+1]][s[now].p[j]]])add(i, s[now].p[j], s[now].p[j+1]);}}for(it = valid.begin(); it != valid.end(); ++it)rep(i, 0, 2)ans.insert(s[*it].p[i]);rep(i, 1, n)if(!ans.count(i))for(it = valid.begin(); it != valid.end(); ++it)if(in_tri(s[*it], i))ans.insert(i);for(it = ans.begin(); it != ans.end(); ++it)ansn[++tot] = name[*it];cout << tot << endl;sort(ansn+1, ansn+tot+1);rep(i, 1, tot)cout << ansn[i] << endl;close_file();return 0;}
大把大把的时光从指缝间遛走，
