Guest User

Untitled

a guest
Jan 23rd, 2018
68
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.85 KB | None | 0 0
  1. #include <fstream.h>
  2. #include <math.h>
  3. #include <stdlib.h>
  4.  
  5. struct point {
  6.     double  x;
  7.     double  y;
  8.     double  angle;
  9. };
  10.  
  11. struct vector {
  12.     double  i;
  13.     double  j;
  14. };
  15.  
  16. point   P[10000];
  17. int     hull[10000];
  18.  
  19. int
  20. zcross (vector * u, vector * v)
  21. {
  22.     double  p = u->i * v->j - v->i * u->j;
  23.     if (p > 0)
  24.     return 1;
  25.     if (p < 0)
  26.     return -1;
  27.     return 0;
  28. }
  29.  
  30. int
  31. cmpP (const void *a, const void *b)
  32. {
  33.     if (((point *) a)->angle < ((point *) b)->angle)
  34.     return -1;
  35.     if (((point *) a)->angle > ((point *) b)->angle)
  36.     return 1;
  37.     return 0;
  38. }
  39.  
  40. void
  41. main ()
  42. {
  43.     int     N, i, hullstart, hullend, a, b;
  44.     double  midx, midy, length;
  45.     vector  v1, v2;
  46.  
  47.     ifstream fin ("fc.in");
  48.     fin >> N;
  49.     midx = 0, midy = 0;
  50.     for (i = 0; i < N; i++) {
  51.     fin >> P[i].x >> P[i].y;
  52.     midx += P[i].x;
  53.     midy += P[i].y;
  54.     }
  55.     fin.close ();
  56.     midx = (double) midx / N;
  57.     midy = (double) midy / N;
  58.     for (i = 0; i < N; i++)
  59.     P[i].angle = atan2 (P[i].y - midy, P[i].x - midx);
  60.     qsort (P, N, sizeof (P[0]), cmpP);
  61.  
  62.     hull[0] = 0;
  63.     hull[1] = 1;
  64.     hullend = 2;
  65.     for (i = 2; i < N - 1; i++) {
  66.     while (hullend > 1) {
  67.         v1.i = P[hull[hullend - 2]].x - P[hull[hullend - 1]].x;
  68.         v1.j = P[hull[hullend - 2]].y - P[hull[hullend - 1]].y;
  69.         v2.i = P[i].x - P[hull[hullend - 1]].x;
  70.         v2.j = P[i].y - P[hull[hullend - 1]].y;
  71.         if (zcross (&v1, &v2) < 0)
  72.         break;
  73.         hullend--;
  74.     }
  75.     hull[hullend] = i;
  76.     hullend++;
  77.     }
  78.  
  79.     while (hullend > 1) {
  80.     v1.i = P[hull[hullend - 2]].x - P[hull[hullend - 1]].x;
  81.     v1.j = P[hull[hullend - 2]].y - P[hull[hullend - 1]].y;
  82.     v2.i = P[i].x - P[hull[hullend - 1]].x;
  83.     v2.j = P[i].y - P[hull[hullend - 1]].y;
  84.     if (zcross (&v1, &v2) < 0)
  85.         break;
  86.     hullend--;
  87.     }
  88.     hull[hullend] = i;
  89.  
  90.     hullstart = 0;
  91.     while (true) {
  92.     v1.i = P[hull[hullend - 1]].x - P[hull[hullend]].x;
  93.     v1.j = P[hull[hullend - 1]].y - P[hull[hullend]].y;
  94.     v2.i = P[hull[hullstart]].x - P[hull[hullend]].x;
  95.     v2.j = P[hull[hullstart]].y - P[hull[hullend]].y;
  96.     if (hullend - hullstart > 1 && zcross (&v1, &v2) >= 0) {
  97.         hullend--;
  98.         continue;
  99.     }
  100.     v1.i = P[hull[hullend]].x - P[hull[hullstart]].x;
  101.     v1.j = P[hull[hullend]].y - P[hull[hullstart]].y;
  102.     v2.i = P[hull[hullstart + 1]].x - P[hull[hullstart]].x;
  103.     v2.j = P[hull[hullstart + 1]].y - P[hull[hullstart]].y;
  104.     if (hullend - hullstart > 1 && zcross (&v1, &v2) >= 0) {
  105.         hullstart++;
  106.         continue;
  107.     }
  108.     break;
  109.     }
  110.  
  111.     length = 0;
  112.     for (i = hullstart; i <= hullend; i++) {
  113.     a = hull[i];
  114.     if (i == hullend)
  115.         b = hull[hullstart];
  116.     else
  117.         b = hull[i + 1];
  118.     length += sqrt ((P[a].x - P[b].x) * (P[a].x - P[b].x) + (P[a].y - P[b].y) * (P[a].y - P[b].y));
  119.     }
  120.  
  121.     ofstream fout ("fc.out");
  122. fout.setf (ios: :fixed);
  123.     fout.precision (2);
  124.     fout << length << '\n';
  125.     fout.close ();
  126. }
Add Comment
Please, Sign In to add comment