Advertisement
Guest User

Untitled

a guest
May 22nd, 2015
205
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.33 KB | None | 0 0
  1. #include <iostream>
  2. #include <stdlib.h>
  3. #include <stdio.h>
  4. #include <algorithm>
  5. #include <math.h>
  6.  
  7. using namespace std;
  8.  
  9. static const int N = 1000;
  10.  
  11. struct vektor
  12. {
  13. int x, y;
  14. };
  15.  
  16. long long vp(vektor a, vektor b)
  17. {
  18. long long p1 = a.x;
  19. long long p2 = b.x;
  20. p1 *= b.y;
  21. p2 *= a.y;
  22. return p1 - p2;
  23. }
  24.  
  25. int n;
  26. vektor niz[N];
  27. int next[N];
  28. int prev[N];
  29. vektor convex[N];
  30.  
  31. bool lower(int i, int j)
  32. {
  33. if(niz[i].y < niz[j].y)
  34. return 1;
  35. if(niz[i].y == niz[j].y)
  36. if(niz[i].x < niz[j].x)
  37. return 1;
  38. return 0;
  39. }
  40.  
  41. bool compare(vektor a, vektor b)
  42. {
  43. vektor v1, v2;
  44. v1.x = a.x - niz[n - 1].x;
  45. v2.x = b.x - niz[n - 1].x;
  46. v1.y = a.y - niz[n - 1].y;
  47. v2.y = b.y - niz[n - 1].y;
  48.  
  49. long long sol = vp(v1, v2);
  50.  
  51. return (sol > 0);
  52. }
  53.  
  54. bool ok(int cur)
  55. {
  56. vektor v1, v2;
  57. v1.x = convex[cur].x - convex[cur - 1].x;
  58. v1.y = convex[cur].y - convex[cur - 1].y;
  59. v2.x = convex[cur - 1].x - convex[cur - 2].x;
  60. v2.y = convex[cur - 1].y - convex[cur - 2].y;
  61. return (vp(v1, v2) < 0);
  62. }
  63.  
  64. double duz(vektor v)
  65. {
  66. double res1 = v.x;
  67. double res2 = v.y;
  68. res1 *= res1;
  69. res2 *= res2;
  70. res1 += res2;
  71. return sqrt(res1);
  72. }
  73.  
  74. double dist(int a, int b, int c)
  75. {
  76. vektor u = convex[c];
  77. vektor v = convex[b];
  78. u.x -= v.x;
  79. u.y -= v.y;
  80. vektor k = convex[a];
  81. k.x -= v.x;
  82. k.y -= v.y;
  83. double sin = ((double) k.x * u.y) - ((double) k.y * u.x);
  84. sin /= duz(u);
  85. if(sin < 0)
  86. sin *= -1;
  87. return sin;
  88. }
  89.  
  90. double povrs(int a, int c, int b, int d)
  91. {
  92. // printf("%i %i %i %i\n", a, b, c, d);
  93. vektor v = convex[a];
  94. vektor u = convex[c];
  95. u.x -= v.x;
  96. u.y -= v.y;
  97. double dz = duz(u);
  98. double res = 0;
  99. res += dist(b, a, c);
  100. res += dist(d, a, c);
  101. res /= 2;
  102. res *= dz;
  103. // printf("%lf\n\n", res);
  104. return res;
  105. }
  106.  
  107. int main()
  108. {
  109. freopen("input.txt", "r", stdin);
  110. scanf("%i", &n);
  111. while(n != -1)
  112. {
  113. for(int i = 0; i < n; i++)
  114. {
  115. scanf("%i", &niz[i].x);
  116. scanf("%i", &niz[i].y);
  117. }
  118. int extreme = 0;
  119. for(int i = 1; i < n; i++)
  120. if(lower(i, extreme))
  121. extreme = i;
  122. swap(niz[n - 1], niz[extreme]);
  123. sort(niz, niz + n - 1, compare);
  124. /*
  125. printf("\n %i %i\n", niz[n - 1].x, niz[n - 1].y);
  126. for(int i = 0; i < n - 1; i++)
  127. printf("%i %i\n", niz[i].x, niz[i].y);
  128. scanf("%i", &n);
  129. */
  130. convex[0] = niz[n - 1];
  131. convex[1] = niz[0];
  132. int cur = 2;
  133. for(int i = 1; i < n - 1; i++)
  134. {
  135. convex[cur] = niz[i];
  136. while(cur > 2 && !ok(cur))
  137. {
  138. swap(convex[cur], convex[cur - 1]);
  139. cur--;
  140. }
  141. cur++;
  142. }
  143. /*
  144. for(int i = 0; i < cur; i++)
  145. printf("%i %i\n", convex[i].x, convex[i].y);
  146. printf("\n\n");
  147. */
  148. double best = 0;
  149. if(cur > 3)
  150. {
  151. for(int i = 0; i < cur; i++)
  152. {
  153. next[i] = (i + 1) % cur;
  154. prev[i] = (i - 1) % cur;
  155. }
  156. for(int i = 0; i < cur; i++)
  157. {
  158. int n = cur;
  159. int d = next[i];
  160. int m = next[d];
  161. int j = m;
  162. for(int g = next[m]; g != i; g = next[g])
  163. if(dist(g, i, j)> dist(m, i, j))
  164. m = g;
  165. int g = m;
  166. //printf("%i %i %i %i\n", i, (i + 2) % n, d, g);
  167. if(povrs(i, j, d, g) > best)
  168. best = povrs(i, j, d, g);
  169. for(j = next[j]; j != prev[i]; j = next[j])
  170. {
  171. while(dist(next[g], i, j) > dist(g, i, j) && g != i)
  172. g = next[g];
  173. while(dist(next[d], i, j) > dist(d, i, j) && d != j)
  174. d = next[g];
  175. //printf("%i %i %i %i\n", i, j, d, g);
  176. if(povrs(i, j, d, g) > best)
  177. best = povrs(i, j, d, g);
  178. }
  179. }
  180. }
  181. if(cur == 3)
  182. {
  183. best = -1;
  184. for(int i = 0; i < n; i++)
  185. {
  186. int k = 0;
  187. for(int j = 0; j < cur; j++)
  188. if(convex[j].x == niz[i].x && convex[j].y == niz[i].y)
  189. k = 1;
  190. if(!k)
  191. {
  192. //printf("%i %i\n", niz[i].x, niz[i].y);
  193. convex[3] = niz[i];
  194. for(int j = 0; j < 3; j++)
  195. {
  196. vektor v = convex[j];
  197. vektor u = convex[(j + 1) % 3];
  198. u.x -= v.x;
  199. u.y -= v.y;
  200. double pom = duz(u);
  201. pom /= 2;
  202. pom *= dist(3, j, (j + 1) % 3);
  203. if(pom < best || best == -1)
  204. best = pom;
  205. }
  206. }
  207. }
  208. best += povrs(0, 1, 0, 2);
  209. }
  210. printf("%lf\n", best);
  211. scanf("%i", &n);
  212. }
  213. return 0;
  214. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement