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
stdin
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
Standard output is empty