fork(1) download
copy 
  1. // seems to work on https://i...content-available-to-author-only...r.edu/index.php?option=com_onlinejudge&Itemid=8&category=387&page=show_problem&problem=3091
  2.  
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. typedef long long ll;
  7. typedef long double ld; 
  8. typedef double db; 
  9. typedef string str; 
  10.  
  11. typedef pair<int, int> pi;
  12. typedef pair<ll,ll> pl; 
  13. typedef pair<ld,ld> pd; 
  14. #define mp make_pair
  15. #define f first
  16. #define s second
  17.  
  18. typedef vector<int> vi; 
  19. typedef vector<ll> vl; 
  20. typedef vector<ld> vd; 
  21. typedef vector<str> vs; 
  22. typedef vector<pi> vpi; 
  23. typedef vector<pl> vpl; 
  24. typedef vector<pd> vpd; 
  25.  
  26. #define sz(x) (int)x.size()
  27. #define all(x) begin(x), end(x)
  28. #define rall(x) (x).rbegin(), (x).rend() 
  29. #define rsz resize
  30. #define ins insert 
  31. #define ft front() 
  32. #define bk back() 
  33. #define pf push_front 
  34. #define pb push_back
  35. #define eb emplace_back 
  36. #define lb lower_bound 
  37. #define ub upper_bound 
  38.  
  39. #define FOR(i,a,b) for (int i = (a); i < (b); ++i)
  40. #define F0R(i,a) FOR(i,0,a)
  41. #define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
  42. #define R0F(i,a) ROF(i,0,a)
  43. #define trav(a,x) for (auto& a: x)
  44.  
  45. const int MOD = 1e9+7; // 998244353; // = (119<<23)+1
  46. const int MX = 2e5+5; 
  47. const ll INF = 1e18; 
  48. const ld PI = 4*atan((ld)1); 
  49. const int xd[4] = {0,1,0,-1}, yd[4] = {1,0,-1,0}; 
  50.  
  51. template<class T> bool ckmin(T& a, const T& b) { 
  52. 	return a > b ? a = b, 1 : 0; }
  53. template<class T> bool ckmax(T& a, const T& b) { 
  54. 	return a < b ? a = b, 1 : 0; }
  55. mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
  56.  
  57. #include <ext/pb_ds/tree_policy.hpp>
  58. #include <ext/pb_ds/assoc_container.hpp>
  59. using namespace __gnu_pbds;
  60.  
  61. template <class T> using Tree = tree<T, null_type, less<T>, 
  62. 	rb_tree_tag, tree_order_statistics_node_update>; 
  63. // change null_type for map
  64. #define ook order_of_key
  65. #define fbo find_by_order
  66.  
  67. void treeExample() {
  68. 	Tree<int> t, t2; t.insert(8);
  69. 	auto it = t.insert(10).f; assert(it == t.lb(9));
  70. 	assert(t.ook(10) == 1); assert(t.ook(11) == 2);
  71. 	assert(*t.fbo(0) == 8);
  72. 	t.join(t2); // assuming T < T2 or T > T2, merge t2 into t
  73. }
  74.  
  75. namespace input {
  76. 	template<class T> void re(complex<T>& x);
  77. 	template<class T1, class T2> void re(pair<T1,T2>& p);
  78. 	template<class T> void re(vector<T>& a);
  79. 	template<class T, size_t SZ> void re(array<T,SZ>& a);
  80.  
  81. 	template<class T> void re(T& x) { cin >> x; }
  82. 	void re(double& x) { string t; re(t); x = stod(t); }
  83. 	void re(ld& x) { string t; re(t); x = stold(t); }
  84. 	template<class T, class... Ts> void re(T& t, Ts&... ts) { 
  85. 		re(t); re(ts...); 
  86. 	}
  87.  
  88. 	template<class T> void re(complex<T>& x) { T a,b; re(a,b); x = cd(a,b); }
  89. 	template<class T1, class T2> void re(pair<T1,T2>& p) { re(p.f,p.s); }
  90. 	template<class T> void re(vector<T>& a) { F0R(i,sz(a)) re(a[i]); }
  91. 	template<class T, size_t SZ> void re(array<T,SZ>& a) { F0R(i,SZ) re(a[i]); }
  92. }
  93.  
  94. using namespace input;
  95.  
  96. namespace output {
  97. 	void pr(int x) { cout << x; }
  98. 	void pr(long x) { cout << x; }
  99. 	void pr(ll x) { cout << x; }
  100. 	void pr(unsigned x) { cout << x; }
  101. 	void pr(unsigned long x) { cout << x; }
  102. 	void pr(unsigned long long x) { cout << x; }
  103. 	void pr(float x) { cout << x; }
  104. 	void pr(double x) { cout << x; }
  105. 	void pr(ld x) { cout << x; }
  106. 	void pr(char x) { cout << x; }
  107. 	void pr(const char* x) { cout << x; }
  108. 	void pr(const string& x) { cout << x; }
  109. 	void pr(bool x) { pr(x ? "true" : "false"); }
  110. 	template<class T> void pr(const complex<T>& x) { cout << x; }
  111.  
  112. 	template<class T1, class T2> void pr(const pair<T1,T2>& x);
  113. 	template<class T> void pr(const T& x);
  114.  
  115. 	template<class T, class... Ts> void pr(const T& t, const Ts&... ts) { 
  116. 		pr(t); pr(ts...); 
  117. 	}
  118. 	template<class T1, class T2> void pr(const pair<T1,T2>& x) { 
  119. 		pr("{",x.f,", ",x.s,"}"); 
  120. 	}
  121. 	template<class T> void pr(const T& x) { 
  122. 		pr("{"); // const iterator needed for vector<bool>
  123. 		bool fst = 1; for (const auto& a: x) pr(!fst?", ":"",a), fst = 0; 
  124. 		pr("}");
  125. 	}
  126.  
  127. 	void ps() { pr("\n"); } // print w/ spaces
  128. 	template<class T, class... Ts> void ps(const T& t, const Ts&... ts) { 
  129. 		pr(t); if (sizeof...(ts)) pr(" "); ps(ts...); 
  130. 	}
  131.  
  132. 	void pc() { pr("]\n"); } // debug w/ commas
  133. 	template<class T, class... Ts> void pc(const T& t, const Ts&... ts) { 
  134. 		pr(t); if (sizeof...(ts)) pr(", "); pc(ts...); 
  135. 	}
  136. 	#define dbg(x...) pr("[",#x,"] = ["), pc(x);
  137. }
  138.  
  139. using namespace output;
  140.  
  141. namespace io {
  142. 	void setIn(string s) { freopen(s.c_str(),"r",stdin); }
  143. 	void setOut(string s) { freopen(s.c_str(),"w",stdout); }
  144. 	void setIO(string s = "") {
  145. 		ios_base::sync_with_stdio(0); cin.tie(0); // fast I/O
  146. 		// cin.exceptions(cin.failbit); // ex. throws exception when you try to read letter into int
  147. 		if (sz(s)) { setIn(s+".in"), setOut(s+".out"); } // for USACO
  148. 	}
  149. }
  150.  
  151. using namespace io;
  152.  
  153. struct mi {
  154. 	typedef decay<decltype(MOD)>::type T;
  155. 	T val; 
  156. 	explicit operator T() const { return val; }
  157. 	mi() { val = 0; }
  158. 	mi(ll v) { 
  159. 		val = (-MOD <= v && v <= MOD) ? v : v % MOD;
  160. 		if (val < 0) val += MOD;
  161. 	}
  162. 	friend bool operator==(const mi& a, const mi& b) { 
  163. 		return a.val == b.val; }
  164. 	friend bool operator!=(const mi& a, const mi& b) { 
  165. 		return !(a == b); }
  166. 	friend bool operator<(const mi& a, const mi& b) { 
  167. 		return a.val < b.val; }
  168. 	friend void re(mi& a) { ll x; re(x); a = mi(x); }
  169. 	friend void pr(const mi& a) { pr(a.val); }
  170. 	friend ostream& operator<<(ostream& os, const mi& a) { 
  171. 		return os << a.val; }
  172.  
  173. 	mi operator-() const { return mi(-val); }
  174. 	mi& operator+=(const mi& m) { 
  175. 		if ((val += m.val) >= MOD) val -= MOD; 
  176. 		return *this; }
  177. 	mi& operator-=(const mi& m) { 
  178. 		if ((val -= m.val) < 0) val += MOD; 
  179. 		return *this; }
  180. 	mi& operator++() { return *this += 1; }
  181. 	mi& operator--() { return *this -= 1; }
  182. 	friend mi operator+(mi a, const mi& b) { return a += b; }
  183. 	friend mi operator-(mi a, const mi& b) { return a -= b; }
  184.  
  185. 	mi& operator*=(const mi& m) { 
  186. 		val = (ll)val*m.val%MOD; return *this; }
  187. 	friend mi pow(mi a, ll p) {
  188. 		mi ans = 1; assert(p >= 0);
  189. 		for (; p; p /= 2, a *= a) if (p&1) ans *= a;
  190. 		return ans;
  191. 	}
  192. 	friend mi inv(const mi& a) { 
  193. 		assert(!(a == 0)); return pow(a,MOD-2); }
  194. 	mi& operator/=(const mi& m) { return (*this) *= inv(m); }
  195. 	friend mi operator*(mi a, const mi& b) { return a *= b; }
  196. 	friend mi operator/(mi a, const mi& b) { return a /= b; }
  197. };
  198. typedef pair<mi,mi> pmi;
  199. typedef vector<mi> vmi;
  200. typedef vector<pmi> vpmi;
  201.  
  202. typedef ld T;
  203. int sgn(T x) { return (x>0)-(x<0); }
  204. T sq(T x) { return x*x; }
  205.  
  206. namespace Point3D {
  207. 	typedef array<T,3> P3;
  208. 	typedef array<P3,3> tri;
  209. 	typedef vector<P3> vP3;
  210. 	T norm(const P3& x) { 
  211. 		T sum = 0; F0R(i,sz(x)) sum += sq(x[i]);
  212. 		return sum; }
  213. 	T abs(const P3& x) { return sqrt(norm(x)); }
  214.  
  215. 	P3& operator+=(P3& l, const P3& r) { 
  216. 		F0R(i,3) l[i] += r[i]; 
  217. 		return l; }
  218. 	P3& operator-=(P3& l, const P3& r) { 
  219. 		F0R(i,3) l[i] -= r[i]; 
  220. 		return l; }
  221. 	P3& operator*=(P3& l, const T& r) { 
  222. 		F0R(i,3) l[i] *= r; 
  223. 		return l; }
  224. 	P3& operator/=(P3& l, const T& r) { 
  225. 		F0R(i,3) l[i] /= r; 
  226. 		return l; }
  227. 	P3 operator+(P3 l, const P3& r) { return l += r; }
  228. 	P3 operator-(P3 l, const P3& r) { return l -= r; }
  229. 	P3 operator*(P3 l, const T& r) { return l *= r; }
  230. 	P3 operator*(const T& r, const P3& l) { return l*r; }
  231. 	P3 operator/(P3 l, const T& r) { return l /= r; }
  232.  
  233. 	P3 unit(const P3& x) { return x/abs(x); }
  234. 	T dot(const P3& a, const P3& b) { 
  235. 		T sum = 0; F0R(i,3) sum += a[i]*b[i]; 
  236. 		return sum; }
  237. 	P3 cross(const P3& a, const P3& b) {
  238. 		return {a[1]*b[2]-a[2]*b[1],a[2]*b[0]-a[0]*b[2],
  239. 				a[0]*b[1]-a[1]*b[0]}; }
  240. 	P3 cross(const P3& a, const P3& b, const P3& c) {
  241. 		return cross(b-a,c-a); }
  242. 	P3 perp(const P3& a, const P3& b, const P3& c) {
  243. 		return unit(cross(a,b,c)); }
  244.  
  245. 	bool isMult(const P3& a, const P3& b) { // for long longs
  246. 		P3 c = cross(a,b); F0R(i,sz(c)) if (c[i] != 0) return 0; 
  247. 		return 1; }
  248. 	bool collinear(const P3& a, const P3& b, const P3& c) { 
  249. 		return isMult(b-a,c-a); }
  250. 	bool coplanar(const P3&a,const P3&b,const P3&c,const P3&d) { 
  251. 		return isMult(cross(b-a,c-a),cross(b-a,d-a)); }
  252. 	bool op(const P3& a, const P3& b) { 
  253. 		int ind = 0; // going in opposite directions?
  254. 		FOR(i,1,3) if (std::abs(a[i]*b[i])>std::abs(a[ind]*b[ind])) 
  255. 			ind = i;
  256. 		return a[ind]*b[ind] < 0;
  257. 	}
  258. 	// coplanar points, b0 and b1 on opposite sides of a0-a1?
  259. 	bool opSide(const P3&a,const P3&b,const P3&c,const P3&d) { 
  260. 		return op(cross(a,b,c),cross(a,b,d)); }
  261. 	// coplanar points, is a in triangle b
  262. 	bool inTri(const P3& a, const tri& b) { 
  263. 		F0R(i,3)if(opSide(b[i],b[(i+1)%3],b[(i+2)%3],a))return 0;
  264. 		return 1; }
  265.  
  266. 	// point-seg dist
  267. 	T psDist(const P3&p,const P3&a,const P3&b) { 
  268. 		if (dot(a-p,a-b) <= 0) return abs(a-p);
  269. 		if (dot(b-p,b-a) <= 0) return abs(b-p);
  270. 		return abs(cross(p,a,b))/abs(a-b);
  271. 	}
  272. 	// projection onto line
  273. 	P3 foot(const P3& p, const P3& a, const P3& b) { 
  274. 		P3 d = unit(b-a); return a+dot(p-a,d)*d; }
  275. 	// rotate p about axis
  276. 	P3 rotAxis(const P3& p, const P3& a, const P3& b, T theta) {
  277. 		P3 dz = unit(b-a), f = foot(p,a,b); 
  278. 		P3 dx = p-f, dy = cross(dz,dx);
  279. 		return f+cos(theta)*dx+sin(theta)*dy;
  280. 	}
  281. 	// projection onto plane
  282. 	P3 foot(const P3& a, const tri& b) {
  283. 		P3 c = perp(b[0],b[1],b[2]);
  284. 		return a-c*(dot(a,c)-dot(b[0],c)); }
  285. 	// line-plane intersection
  286. 	P3 lpIntersect(const P3&a0,const P3&a1,const tri&b) { 
  287. 		P3 c = unit(cross(b[2]-b[0],b[1]-b[0]));
  288. 		T x = dot(a0,c)-dot(b[0],c), y = dot(a1,c)-dot(b[0],c);
  289. 		return (y*a0-x*a1)/(y-x);
  290. 	}
  291. }
  292. using namespace Point3D;
  293.  
  294. bool onSameHalfSpace(P3 a, P3 b, P3 p1, P3 p2, P3 p3) {
  295. 	P3 hlp = cross(p2-p1,p3-p1);
  296. 	return dot(hlp,a-p1)*dot(hlp,b-p1) >= 0;
  297. }
  298. map<array<int,3>,int> hull;
  299. void toggle(int i1, int i2, int i3, int ref) {
  300. 	array<int,3> a = {i1,i2,i3};
  301. 	if (hull.count(a)) hull.erase(a);
  302. 	else hull[a] = ref;
  303. }
  304.  
  305. void makeHull(vP3& pts) {
  306. 	FOR(i,1,sz(pts)) if (pts[0] != pts[i]) swap(pts[1],pts[i]); 
  307. 	FOR(i,2,sz(pts)) if (!collinear(pts[0],pts[1],pts[i])) swap(pts[2],pts[i]); 
  308. 	FOR(i,3,sz(pts)) if (!coplanar(pts[0],pts[1],pts[2],pts[i])) swap(pts[3],pts[i]); 
  309. 	hull[{0,1,2}]=3; hull[{0,1,3}]=2; hull[{0,2,3}]=1; hull[{1,2,3}]=0;
  310.  
  311. 	// ps("WUT",pts);
  312. 	FOR(i,4,sz(pts)) {
  313. 		vector<pair<pair<int,int>,pair<int,int>>> toChange;
  314. 		trav(face,hull) {
  315. 			int i1 = face.f[0], i2 = face.f[1], i3 = face.f[2];
  316. 			P3 pt1 = pts[i1], pt2 = pts[i2], pt3 = pts[i3];
  317. 			P3 ref = pts[face.s];
  318. 			if (!onSameHalfSpace(pts[i],ref,pt1,pt2,pt3)) {
  319. 				toChange.pb({{i1,i2},{i,i3}});
  320. 				toChange.pb({{i1,i3},{i,i2}});
  321. 				toChange.pb({{i2,i3},{i,i1}});
  322. 				toChange.pb({{i1,i2},{i3,i}});
  323. 			}
  324. 		}
  325. 		trav(diff,toChange) 
  326. 			toggle(diff.f.f,diff.f.s,diff.s.f, diff.s.s);
  327. 	}
  328. }
  329.  
  330. /*T signedPolyVolume(const vP3& p, const vector<F>& trilist) {
  331. 	T v = 0;
  332. 	trav(i,trilist) v += dot(cross(p[i.a],p[i.b]),p[i.c]);
  333. 	return v/6;
  334. }*/
  335.  
  336. int main() {
  337. 	ios_base::sync_with_stdio(0); cin.tie(0);
  338. 	cout << fixed << setprecision(4);
  339. 	int N;
  340. 	while (cin >> N) {
  341. 		hull.clear();
  342. 		vP3 v(N); re(v);
  343. 		makeHull(v);
  344. 		set<P3> faces;
  345. 		ld vol = 0, sa = 0;
  346. 		trav(t,hull) {
  347. 			auto T = t.f;
  348. 			if (onSameHalfSpace(v[T[0]]+cross(v[T[0]],v[T[1]],v[T[2]]),v[t.s],v[T[0]],v[T[1]],v[T[2]]))
  349. 				swap(T[0],T[1]);
  350. 			faces.insert(unit(cross(v[T[0]],v[T[1]],v[T[2]])));
  351. 			// vol += dot(cross(v[T[0]],v[T[1]]),v[T[2]]);
  352. 			// sa += abs(cross(v[T[0]],v[T[1]],v[T[2]]));
  353. 			//ps("FACE",v[T[0]],v[T[1]],v[T[2]]);
  354. 			// ps("AH",v[T[0]],v[T[1]],v[T[2]],v[t.s]);
  355. 			//ps(cross(v[T[0]],v[T[1]],v[T[2]]),v[t.s]);
  356. 		}
  357. 		// trav(t,faces) ps(t);
  358. 		ps(sz(faces));
  359. 	}
  360. 	/*
  361. 	vP3 v;
  362. 	v.pb({0,0,0}); 
  363. 	v.pb({1,0,0}); 
  364. 	v.pb({0,1,0}); 
  365. 	v.pb({0,0,1}); 
  366. 	// F0R(i,8) v.pb(P3{i/4%2,i/2%2,i%2});
  367. 	F0R(i,64) v.pb(P3{i/16%4,i/4%4,i%4});
  368. 	random_shuffle(all(v));
  369. 	makeHull(v);
  370. 	*/
  371. 	// you should actually read the stuff at the bottom
  372. }
  373.  
  374. /* stuff you should look for
  375. 	* int overflow, array bounds
  376. 	* special cases (n=1?), slow multiset operations
  377. 	* do smth instead of nothing and stay organized
  378. */
Success #stdin #stdout 0s 4388KB
comments (?)
stdin
copy 
7
1 1 0
1 -1 0
-1 1 0
-1 -1 0
0 0 1
0 0 0
0 0 -0.1
7
1 1 0
1 -1 0
-1 1 0
-1 -1 0
0 0 1
0 0 0
0 0 0.1
stdout
copy 
8
5
https://ideone.com/ZVPDZm
3Dhull test (Public)
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!