Problem - 3662

  题意很简单,构造三维凸包,求凸包有多少个面。

代码如下:

 #include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath> using namespace std; const double EPS = 1e-;
const int N = ;
inline int sgn(double x) { return (x > EPS) - (x < -EPS);}
struct Point {
double x, y, z;
Point() {}
Point(double x, double y, double z) : x(x), y(y), z(z) {}
bool operator < (Point a) const {
if (sgn(x - a.x)) return x < a.x;
if (sgn(y - a.y)) return y < a.y;
return z < a.z;
}
bool operator == (Point a) const { return !sgn(x - a.x) && !sgn(y - a.y) && !sgn(z - a.z);}
Point operator + (Point a) { return Point(x + a.x, y + a.y, z + a.z);}
Point operator - (Point a) { return Point(x - a.x, y - a.y, z - a.z);}
Point operator * (double p) { return Point(x * p, y * p, z * p);}
Point operator / (double p) { return Point(x / p, y / p, z / p);}
} ;
inline double dot(Point a, Point b) { return a.x * b.x + a.y * b.y + a.z * b.z;}
inline double dot(Point o, Point a, Point b) { return dot(a - o, b - o);}
inline Point cross(Point a, Point b) { return Point(a.y * b.z - a.z * b.y, a.z * b.x - a.x * b.z, a.x * b.y - a.y * b.x);}
inline Point cross(Point o, Point a, Point b) { return cross(a - o, b - o);}
inline double veclen(Point x) { return sqrt(dot(x, x));}
inline double area(Point o, Point a, Point b) { return veclen(cross(o, a, b)) / 2.0;}
inline double volume(Point o, Point a, Point b, Point c) { return dot(cross(o, a, b), c - o) / 6.0;} struct _3DCH{
Point pt[N];
int pcnt;
struct Face {
int a, b, c;
bool ok;
Face() {}
Face(int a, int b, int c) : a(a), b(b), c(c) { ok = true;}
} fc[N << ];
int fcnt;
int fid[N][N]; bool outside(int p, int a, int b, int c) { return sgn(volume(pt[a], pt[b], pt[c], pt[p])) < ;}
bool outside(int p, int f) { return outside(p, fc[f].a, fc[f].b, fc[f].c);}
void addface(int a, int b, int c, int d) {
if (outside(d, a, b, c)) fc[fcnt] = Face(c, b, a), fid[c][b] = fid[b][a] = fid[a][c] = fcnt++;
else fc[fcnt] = Face(a, b, c), fid[a][b] = fid[b][c] = fid[c][a] = fcnt++;
} bool dfs(int p, int f) {
if (!fc[f].ok) return true;
int a = fc[f].a, b = fc[f].b, c = fc[f].c;
if (outside(p, a, b, c)) {
fc[f].ok = false;
if (!dfs(p, fid[b][a])) addface(p, a, b, c);
if (!dfs(p, fid[c][b])) addface(p, b, c, a);
if (!dfs(p, fid[a][c])) addface(p, c, a, b);
return true;
}
return false;
}
void build() {
bool ok;
fcnt = ;
sort(pt, pt + pcnt);
pcnt = unique(pt, pt + pcnt) - pt;
ok = false;
for (int i = ; i < pcnt; i++) {
if (sgn(area(pt[], pt[], pt[i]))) {
ok = true;
swap(pt[i], pt[]);
break;
}
}
if (!ok) return ;
ok = false;
for (int i = ; i < pcnt; i++) {
if (sgn(volume(pt[], pt[], pt[], pt[i]))) {
ok = true;
swap(pt[i], pt[]);
break;
}
}
if (!ok) return ;
addface(, , , );
addface(, , , );
addface(, , , );
addface(, , , );
for (int i = ; i < pcnt; i++) {
for (int j = fcnt - ; j >= ; j--) {
if (outside(i, j)) {
dfs(i, j);
break;
}
}
}
int sz = fcnt;
fcnt = ;
for (int i = ; i < sz; i++) if (fc[i].ok) fc[fcnt++] = fc[i];
}
double facearea() {
double ret = 0.0;
for (int i = ; i < fcnt; i++) ret += area(pt[fc[i].a], pt[fc[i].b], pt[fc[i].c]);
return ret;
}
bool same(int i, int j) {
int a = fc[i].a, b = fc[i].b, c = fc[i].c;
if (sgn(volume(pt[a], pt[b], pt[c], pt[fc[j].a]))) return false;
if (sgn(volume(pt[a], pt[b], pt[c], pt[fc[j].b]))) return false;
if (sgn(volume(pt[a], pt[b], pt[c], pt[fc[j].c]))) return false;
return true;
}
int facecnt() {
int cnt = ;
for (int i = ; i < fcnt; i++) {
bool ok = true;
for (int j = ; j < i; j++) {
if (same(i, j)) {
ok = false;
break;
}
}
if (ok) cnt++;
}
return cnt;
}
} ch; int main() {
// freopen("in", "r", stdin);
int n;
double x, y, z;
while (~scanf("%d", &ch.pcnt)) {
for (int i = ; i < ch.pcnt; i++) {
scanf("%lf%lf%lf", &x, &y, &z);
ch.pt[i] = Point(x, y, z);
}
ch.build();
// printf("%.3f\n", ch.facearea());
printf("%d\n", ch.facecnt());
}
return ;
}

  三维凸包还是挺简单的,不用抄模板也能敲出来。不过,还不熟练,敲了接近一个钟。

——written by Lyon

最新文章

  1. Python基础(二)之字符串
  2. sql 增加字段
  3. php7.0 redis扩展下载地址
  4. gc overhead limit exceeded
  5. html meta标签用法详细介绍
  6. (转)if语句优化
  7. weblogic启动问题
  8. HTML5 页面制作工具
  9. Swagger: 一个restful接口文档在线生成+功能测试软件
  10. java操作svn工具类SvnUtil
  11. pytorch Debug —交互式调试工具Pdb (ipdb是增强版的pdb)-1-使用说明
  12. kali安装Google浏览器之后的问题
  13. pandas 常用清洗数据(二)
  14. css 题目笔记(本文收集了一些个人觉得比较有意思的css题目,欢迎大家给出自己的解答)
  15. python清空列表的方法
  16. Java入门系列(一)基础概览
  17. MS EXCEL2013添加Oracle Web ADI菜单
  18. EXPLAIN sql优化方法(2) Using temporary ; Using filesort
  19. 第三节 循环链表的Go语言实现
  20. JS-排序详解:冒泡排序、选择排序和快速排序

热门文章

  1. day36 09-Hibernate中的事务:事务处理
  2. python 数字编码
  3. Leetcode33.Search in Rotated Sorted Array搜索旋转排序数组
  4. PhpStorm中如何配置SVN,详细操作方法 - 郑加全的博客 - CSDN博客
  5. js 正则去除html代码
  6. 【每日一linux命令7】用户及用户组
  7. 存储过程详解 -SQLServer
  8. python 结构化的数据
  9. $.ajax中contentType: “application/json” 的用法
  10. day39-Spring 03-JDK的动态代理