Advertisement
Guest User

Untitled

a guest
Jan 7th, 2016
327
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 7.45 KB | None | 0 0
  1. #include <cstdio>
  2. #include <cstring>
  3. #include <iostream>
  4. #include <algorithm>
  5. #include <cmath>
  6. using namespace std;
  7.  
  8. const int MAXN = 110;
  9. const double EPS = 1e-8;
  10. const double PI = acos(-1.0);//3.14159265358979323846
  11.  
  12. inline int sgn(double x) {
  13. return (x > EPS) - (x < -EPS);
  14. }
  15.  
  16. struct Point {
  17. double x, y, ag;
  18. Point() {}
  19. Point(double x, double y): x(x), y(y) {}
  20. void read() {
  21. scanf("%lf%lf", &x, &y);
  22. }
  23. bool operator == (const Point &rhs) const {
  24. return sgn(x - rhs.x) == 0 && sgn(y - rhs.y) == 0;
  25. }
  26. bool operator < (const Point &rhs) const {
  27. if(y != rhs.y) return y < rhs.y;
  28. return x < rhs.x;
  29. }
  30. Point operator + (const Point &rhs) const {
  31. return Point(x + rhs.x, y + rhs.y);
  32. }
  33. Point operator - (const Point &rhs) const {
  34. return Point(x - rhs.x, y - rhs.y);
  35. }
  36. Point operator * (const int &b) const {
  37. return Point(x * b, y * b);
  38. }
  39. Point operator / (const int &b) const {
  40. return Point(x / b, y / b);
  41. }
  42. double length() const {
  43. return sqrt(x * x + y * y);
  44. }
  45. Point unit() const {
  46. return *this / length();
  47. }
  48. };
  49. typedef Point Vector;
  50.  
  51. double dist(const Point &a, const Point &b) {
  52. return (a - b).length();
  53. }
  54.  
  55. double cross(const Point &a, const Point &b) {
  56. return a.x * b.y - a.y * b.x;
  57. }
  58. //ret >= 0 means turn left
  59. double cross(const Point &sp, const Point &ed, const Point &op) {
  60. return sgn(cross(sp - op, ed - op));
  61. }
  62.  
  63. double area(const Point& a, const Point &b, const Point &c) {
  64. return fabs(cross(a - c, b - c)) / 2;
  65. }
  66. //counter-clockwise
  67. Point rotate(const Point &p, double angle, const Point &o = Point(0, 0)) {
  68. Point t = p - o;
  69. double x = t.x * cos(angle) - t.y * sin(angle);
  70. double y = t.y * cos(angle) + t.x * sin(angle);
  71. return Point(x, y) + o;
  72. }
  73.  
  74. struct Seg {
  75. Point st, ed;
  76. double ag;
  77. Seg() {}
  78. Seg(Point st, Point ed): st(st), ed(ed) {}
  79. void read() {
  80. st.read(); ed.read();
  81. }
  82. void makeAg() {
  83. ag = atan2(ed.y - st.y, ed.x - st.x);
  84. }
  85. };
  86. typedef Seg Line;
  87.  
  88. void moveRight(Line &v, double r) {
  89. double dx = v.ed.x - v.st.x, dy = v.ed.y - v.st.y;
  90. dx = dx / dist(v.st, v.ed) * r;
  91. dy = dy / dist(v.st, v.ed) * r;
  92. v.st.x += dy; v.ed.x += dy;
  93. v.st.y -= dx; v.ed.y -= dx;
  94. }
  95.  
  96. bool isOnSeg(const Seg &s, const Point &p) {
  97. return (p == s.st || p == s.ed) ||
  98. (((p.x - s.st.x) * (p.x - s.ed.x) < 0 ||
  99. (p.y - s.st.y) * (p.y - s.ed.y) < 0) &&
  100. sgn(cross(s.ed, p, s.st) == 0));
  101. }
  102.  
  103. bool isIntersected(const Point &s1, const Point &e1, const Point &s2, const Point &e2) {
  104. return (max(s1.x, e1.x) >= min(s2.x, e2.x)) &&
  105. (max(s2.x, e2.x) >= min(s1.x, e1.x)) &&
  106. (max(s1.y, e1.y) >= min(s2.y, e2.y)) &&
  107. (max(s2.y, e2.y) >= min(s1.y, e1.y)) &&
  108. (cross(s2, e1, s1) * cross(e1, e2, s1) >= 0) &&
  109. (cross(s1, e2, s2) * cross(e2, e1, s2) >= 0);
  110. }
  111.  
  112. bool isIntersected(const Seg &a, const Seg &b) {
  113. return isIntersected(a.st, a.ed, b.st, b.ed);
  114. }
  115.  
  116. bool isParallel(const Seg &a, const Seg &b) {
  117. return sgn(cross(a.ed - a.st, b.ed - b.st)) == 0;
  118. }
  119.  
  120. //return Ax + By + C =0 's A, B, C
  121. void Coefficient(const Line &L, double &A, double &B, double &C) {
  122. A = L.ed.y - L.st.y;
  123. B = L.st.x - L.ed.x;
  124. C = L.ed.x * L.st.y - L.st.x * L.ed.y;
  125. }
  126. //point of intersection
  127. Point operator * (const Line &a, const Line &b) {
  128. double A1, B1, C1;
  129. double A2, B2, C2;
  130. Coefficient(a, A1, B1, C1);
  131. Coefficient(b, A2, B2, C2);
  132. Point I;
  133. I.x = - (B2 * C1 - B1 * C2) / (A1 * B2 - A2 * B1);
  134. I.y = (A2 * C1 - A1 * C2) / (A1 * B2 - A2 * B1);
  135. return I;
  136. }
  137.  
  138. bool isEqual(const Line &a, const Line &b) {
  139. double A1, B1, C1;
  140. double A2, B2, C2;
  141. Coefficient(a, A1, B1, C1);
  142. Coefficient(b, A2, B2, C2);
  143. return sgn(A1 * B2 - A2 * B1) == 0 && sgn(A1 * C2 - A2 * C1) == 0 && sgn(B1 * C2 - B2 * C1) == 0;
  144. }
  145.  
  146. struct Poly {
  147. int n;
  148. Point p[MAXN];//p[n] = p[0]
  149. void init(Point *pp, int nn) {
  150. n = nn;
  151. for(int i = 0; i < n; ++i) p[i] = pp[i];
  152. p[n] = p[0];
  153. }
  154. double area() {
  155. if(n < 3) return 0;
  156. double s = p[0].y * (p[n - 1].x - p[1].x);
  157. for(int i = 1; i < n; ++i)
  158. s += p[i].y * (p[i - 1].x - p[i + 1].x);
  159. return s / 2;
  160. }
  161. };
  162.  
  163. void Graham_scan(Point *p, int n, int *stk, int &top) {//stk[0] = stk[top]
  164. sort(p, p + n);
  165. top = 1;
  166. stk[0] = 0; stk[1] = 1;
  167. for(int i = 2; i < n; ++i) {
  168. while(top && cross(p[i], p[stk[top]], p[stk[top - 1]]) >= 0) --top;
  169. stk[++top] = i;
  170. }
  171. int len = top;
  172. stk[++top] = n - 2;
  173. for(int i = n - 3; i >= 0; --i) {
  174. while(top != len && cross(p[i], p[stk[top]], p[stk[top - 1]]) >= 0) --top;
  175. stk[++top] = i;
  176. }
  177. }
  178. //use for half_planes_cross
  179. bool cmpAg(const Line &a, const Line &b) {
  180. if(sgn(a.ag - b.ag) == 0)
  181. return sgn(cross(b.ed, a.st, b.st)) < 0;
  182. return a.ag < b.ag;
  183. }
  184. //clockwise, plane is on the right
  185. bool half_planes_cross(Line *v, int vn, Poly &res, Line *deq) {
  186. int i, n;
  187. sort(v, v + vn, cmpAg);
  188. for(i = n = 1; i < vn; ++i) {
  189. if(sgn(v[i].ag - v[i-1].ag) == 0) continue;
  190. v[n++] = v[i];
  191. }
  192. int head = 0, tail = 1;
  193. deq[0] = v[0], deq[1] = v[1];
  194. for(i = 2; i < n; ++i) {
  195. if(isParallel(deq[tail - 1], deq[tail]) || isParallel(deq[head], deq[head + 1]))
  196. return false;
  197. while(head < tail && sgn(cross(v[i].ed, deq[tail - 1] * deq[tail], v[i].st)) > 0)
  198. --tail;
  199. while(head < tail && sgn(cross(v[i].ed, deq[head] * deq[head + 1], v[i].st)) > 0)
  200. ++head;
  201. deq[++tail] = v[i];
  202. }
  203. while(head < tail && sgn(cross(deq[head].ed, deq[tail - 1] * deq[tail], deq[head].st)) > 0)
  204. --tail;
  205. while(head < tail && sgn(cross(deq[tail].ed, deq[head] * deq[head + 1], deq[tail].st)) > 0)
  206. ++head;
  207. if(tail <= head + 1) return false;
  208. res.n = 0;
  209. for(i = head; i < tail; ++i)
  210. res.p[res.n++] = deq[i] * deq[i + 1];
  211. res.p[res.n++] = deq[head] * deq[tail];
  212. res.n = unique(res.p, res.p + res.n) - res.p;
  213. res.p[res.n] = res.p[0];
  214. return true;
  215. }
  216.  
  217. /*******************************************************************************************/
  218.  
  219. Poly poly;
  220. Line line[MAXN], deq[MAXN];
  221. char str[10];
  222. Point pre, cur;
  223. int n;
  224.  
  225. int main() {
  226. line[n++] = Line(Point(0, 0), Point(0, 10)); line[n - 1].makeAg();
  227. line[n++] = Line(Point(0, 10), Point(10, 10)); line[n - 1].makeAg();
  228. line[n++] = Line(Point(10, 10), Point(10, 0)); line[n - 1].makeAg();
  229. line[n++] = Line(Point(10, 0), Point(0, 0)); line[n - 1].makeAg();
  230. pre = Point(0, 0);
  231. double x, y;
  232. while(scanf("%lf%lf%s", &x, &y, str) != EOF) {
  233. cur = Point(x, y);
  234. Point mid = (cur + pre) / 2;
  235. if(strcmp(str, "Hotter")) {
  236. Point st = rotate(pre, -PI/2, mid);
  237. Point ed = rotate(cur, -PI/2, mid);
  238. line[n++] = Line(st, ed); line[n - 1].makeAg();
  239. }
  240. if(strcmp(str, "Colder")) {
  241. Point st = rotate(pre, PI/2, mid);
  242. Point ed = rotate(cur, PI/2, mid);
  243. line[n++] = Line(st, ed); line[n - 1].makeAg();
  244. }
  245. bool flag = half_planes_cross(line, n, poly, deq);
  246. printf("%.2f\n", flag * (poly.area() + EPS));
  247. pre = cur;
  248. }
  249. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement