fork download
copy 
  1. // BEGIN CUT HERE
  2.  
  3. // END CUT HERE
  4. #line 5 "PolygonRotation.cpp"
  5. #include <bits/stdc++.h>
  6. #define LL long long
  7.  
  8. const double PI = acos(-1.0);
  9. const double EPS = 1e-9;
  10.  
  11. using namespace std;
  12.  
  13. typedef long double CT;
  14. struct Point {
  15.   CT x, y;
  16.   Point() {}
  17.   Point(CT x, CT y) : x(x), y(y) {}
  18.   Point(const Point &p) : x(p.x), y(p.y)    {}
  19.   Point operator + (const Point &p)  const { return Point(x+p.x, y+p.y); }
  20.   Point operator - (const Point &p)  const { return Point(x-p.x, y-p.y); }
  21.   Point operator * (double c)     const { return Point(x*c,   y*c  ); }
  22.   Point operator / (double c)     const { return Point(x/c,   y/c  ); }
  23. 	bool operator<(const Point &other) const {
  24. 		return this->y > other.y;
  25. 	}
  26. };
  27. CT dot(Point p, Point q)     { return p.x*q.x+p.y*q.y; }
  28. double dist2(Point p, Point q)   { return dot(p-q,p-q); }
  29. CT cross(Point p, Point q)   { return p.x*q.y-p.y*q.x; }
  30. ostream &operator<<(ostream &os, const Point &p) {
  31.   os << "(" << p.x << "," << p.y << ")";
  32. 	return os;
  33. }
  34. bool LinesParallel(Point a, Point b, Point c, Point d) {
  35.   return fabs(cross(b-a, c-d)) < EPS;
  36. }
  37. bool LinesCollinear(Point a, Point b, Point c, Point d) {
  38.   return LinesParallel(a, b, c, d)
  39.       && fabs(cross(a-b, a-c)) < EPS
  40.       && fabs(cross(c-d, c-a)) < EPS;
  41. }
  42. // determine if line segment from a to b intersects with
  43. // line segment from c to d
  44. bool SegmentsIntersect(Point a, Point b, Point c, Point d) {
  45.   if (LinesCollinear(a, b, c, d)) {
  46.     if (dist2(a, c) < EPS || dist2(a, d) < EPS ||
  47.       dist2(b, c) < EPS || dist2(b, d) < EPS) return true;
  48.     if (dot(c-a, c-b) > 0 && dot(d-a, d-b) > 0 && dot(c-b, d-b) > 0)
  49.       return false;
  50.     return true;
  51.   }
  52.   if (cross(d-a, b-a) * cross(c-a, b-a) > 0) return false;
  53.   if (cross(a-c, d-c) * cross(b-c, d-c) > 0) return false;
  54.   return true;
  55. }
  56. bool collinear(Point a, Point b, Point c) {
  57. 	return fabs((a.x - c.x) * (b.y - a.y) - (a.x - b.x) * (c.y - a.y)) < EPS;
  58. }
  59. bool on_segment(Point a, Point b, Point x) {
  60.     if(x.x <= max(a.x, b.x) and x.x >= min(a.x, b.x) and
  61.             x.y <= max(a.y, b.y) and x.y >= min(a.y, b.y)) {
  62.         return collinear(a, b, x);
  63.     }
  64.     return false;
  65. }
  66. Point ComputeLineIntersection(Point a, Point b, Point c, Point d) {
  67.   b=b-a; d=c-d; c=c-a;
  68. 	if(! (dot(b, b) > EPS && dot(d, d) > EPS) ) {
  69. 		return Point(-1e18, -1e18);
  70. 	}
  71.   assert(dot(b, b) > EPS && dot(d, d) > EPS);
  72.   return a + b*cross(c, d)/cross(b, d);
  73. }
  74. CT eval(Point p1, Point p2, CT Y) {
  75. 	if(fabs(p1.y - p2.y) < EPS) return p1.x;
  76. 	CT m = (p1.y - p2.y)/(p1.x - p2.x);
  77. 	return ((Y - p1.y)/m) + p1.x;
  78. }
  79.  
  80. const int OFFSET = 110;
  81. bool is_sp[400];
  82. CT maxim[400];
  83.  
  84. class PolygonRotation {
  85. public:
  86. 	CT frustum(CT h, CT R, CT r) {
  87. 		return ((PI * h)/3) * (R*R + R*r + r*r);
  88. 	}
  89. 	double getVolume(vector <int> x, vector <int> y) {
  90. 		vector<Point> l_half, r_half;
  91. 		int split = 0;
  92. 		for(int i = 1; i < x.size(); i++) {
  93. 			if(x[i] == 0) {
  94. 				split = i;
  95. 				break;
  96. 			}
  97. 		}
  98. 		vector<CT> ys;
  99. 		for(int i = 0; i <= split; i++) {
  100. 			l_half.push_back(Point(x[i], y[i]));
  101. 			ys.push_back(y[i]);
  102. 			maxim[y[i] + OFFSET] = max(maxim[y[i] + OFFSET], (CT)x[i]);
  103. 		}
  104. 		r_half.push_back(Point(x[0], y[0]));
  105. 		for(int i = int(x.size()) - 1; i >= split; i--) {
  106. 			r_half.push_back(Point(-x[i], y[i]));
  107. 			ys.push_back(y[i]);
  108. 			maxim[y[i] + OFFSET] = max(maxim[y[i] + OFFSET], (CT)-x[i]);
  109. 		}
  110. 		for(int i = 1; i < l_half.size(); i++) {
  111. 			for(int j = 1; j < r_half.size(); j++) {
  112. 				if(SegmentsIntersect(l_half[i], l_half[i-1], r_half[j], r_half[j-1])) {
  113. 					Point temp = ComputeLineIntersection(l_half[i], l_half[i-1], r_half[j], r_half[j-1]);
  114. 					if(temp.y > -1e10) {
  115. 						ys.push_back(temp.y);
  116. 					}
  117. 				}
  118. 			}
  119. 		}
  120. 		sort(ys.begin(), ys.end());
  121. 		ys.resize(unique(ys.begin(), ys.end()) - ys.begin());
  122. 		CT p_r = -1e9, p_y = -1e9;
  123. 		CT res = 0;
  124. 		for(auto &y: ys) {
  125. 			CT maxim = 0;
  126. 			for(auto &p: l_half) {
  127. 				if(fabs(p.y - y) < EPS) {
  128. 					maxim = max(maxim, p.x);
  129. 				}
  130. 			}
  131. 			for(auto &p: r_half) {
  132. 				if(fabs(p.y - y) < EPS) {
  133. 					maxim = max(maxim, p.x);
  134. 				}
  135. 			}
  136. 			for(int i = 1; i < l_half.size(); i++) {
  137. 				if(l_half[i].y <= y && l_half[i-1].y >= y) {
  138. 					maxim = max(maxim, eval(l_half[i], l_half[i-1], y));
  139. 				}
  140. 			}
  141. 			for(int i = 1; i < r_half.size(); i++) {
  142. 				if(r_half[i].y <= y && r_half[i-1].y >= y) {
  143. 					maxim = max(maxim, eval(r_half[i], r_half[i-1], y));
  144. 				}
  145. 			}
  146. 			if(p_y > -1e3) {
  147. 				CT h = y - p_y;
  148. 				CT R = max(p_r, maxim);
  149. 				CT r = min(p_r, maxim);
  150. 				res += frustum(h, R, r);
  151. 			}
  152. 			p_y = y;
  153. 			p_r = maxim;
  154. 		}
  155. 		return (double)res;
  156. 	}
  157. };
  158.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
/usr/lib/gcc/x86_64-linux-gnu/6/../../../x86_64-linux-gnu/Scrt1.o: In function `_start':
(.text+0x20): undefined reference to `main'
collect2: error: ld returned 1 exit status
stdout
copy 
Standard output is empty
https://ideone.com/OCJcbk
language:
C++14 (gcc 8.3)
created:
7 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!