daily pastebin goal
63%
SHARE
TWEET

123123

a guest May 17th, 2015 11 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. .h
  2. #pragma once
  3.  
  4. struct Point
  5. {
  6. int x;
  7. int y;
  8. };
  9.  
  10.  
  11. class alg
  12. {
  13. public:
  14. alg();
  15. ~alg();
  16.  
  17. //void set_m(int);
  18. //int get_m();
  19.  
  20.  
  21. // A utility function to find next to top in a stack
  22. Point nextToTop();
  23.  
  24. // A utility function to swap two points
  25. void swap(Point, Point);
  26.  
  27. // A utility function to return square of distance between p1 and p2
  28. int dist(Point, Point);
  29.  
  30. int orientation(Point, Point, Point);
  31.  
  32. // A function used by library function qsort() to sort an array of
  33. // points with respect to the first point
  34. int compare(const void, const void );
  35.  
  36. // Prints convex hull of a set of n points.
  37. void convexHull(Point[] , int );
  38.  
  39. };
  40.  
  41. cpp
  42. #include "StdAfx.h"
  43. #include "alg.h"
  44. #include <stack>
  45. #include <stdlib.h>
  46. #include<math.h>
  47. #include <iostream>
  48.  
  49. using namespace std;
  50. using namespace System;
  51.  
  52. Point p0;
  53. alg::alg()
  54. {
  55. }
  56.  
  57. alg::~alg()
  58. {
  59. }
  60.  
  61. Point nextToTop(stack<Point> &S)
  62. {
  63. Point p = S.top();
  64. S.pop();
  65. Point res = S.top();
  66. S.push(p);
  67. return res;
  68. }
  69.  
  70. void swap(Point &p1, Point &p2)
  71. {
  72. Point temp = p1;
  73. p1 = p2;
  74. p2 = temp;
  75. }
  76.  
  77. int dist(Point p1, Point p2)
  78. {
  79. return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
  80. }
  81.  
  82. int orientation(Point p, Point q, Point r)
  83. {
  84. int val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
  85.  
  86. if (val == 0)
  87. return 0; // colinear
  88. return (val > 0) ? 1 : 2; // clock or counterclock wise
  89. }
  90.  
  91. // A function used by library function qsort() to sort an array of
  92. // points with respect to the first point
  93. int compare(const void *vp1, const void *vp2)
  94. {
  95. Point *p1 = (Point *) vp1;
  96. Point *p2 = (Point *) vp2;
  97.  
  98. // Find orientation
  99. int o = orientation(p0, *p1, *p2);
  100. if (o == 0)
  101. return (dist(p0, *p2) >= dist(p0, *p1)) ? -1 : 1;
  102.  
  103. return (o == 2) ? -1 : 1;
  104. }
  105.  
  106. // Prints convex hull of a set of n points.
  107. void convexHull(Point points[], int n)
  108. {
  109. // Find the bottommost point
  110. int ymin = points[0].y, min = 0;
  111. for (int i = 1; i < n; i++)
  112. {
  113. int y = points[i].y;
  114.  
  115. // Pick the bottom-most or chose the left most point in case of tie
  116. if ((y < ymin) || (ymin == y && points[i].x < points[min].x))
  117. ymin = points[i].y, min = i;
  118. }
  119.  
  120. // Place the bottom-most point at first position
  121. swap(points[0], points[min]);
  122.  
  123. // Sort n-1 points with respect to the first point. A point p1 comes
  124. // before p2 in sorted ouput if p2 has larger polar angle (in
  125. // counterclockwise direction) than p1
  126. p0 = points[0];
  127. qsort(&points[1], n - 1, sizeof(Point), compare);
  128.  
  129. // Create an empty stack and push first three points to it.
  130. stack<Point> S;
  131. S.push(points[0]);
  132. S.push(points[1]);
  133. S.push(points[2]);
  134.  
  135. // Process remaining n-3 points
  136. for (int i = 3; i < n; i++)
  137. {
  138. // Keep removing top while the angle formed by points next-to-top,
  139. // top, and points[i] makes a non-left turn
  140. while (orientation(nextToTop(S), S.top(), points[i]) != 2)
  141. S.pop();
  142. S.push(points[i]);
  143. }
  144.  
  145. // Now stack has the output points, print contents of stack
  146. while (!S.empty())
  147. {
  148. Point p = S.top();
  149. cout « "(" « p.x « ", " « p.y « ")" « endl;
  150. S.pop();
  151. }
  152. }
  153.  
  154.  
  155. main
  156. #include "StdAfx.h"
  157. #include <iostream>
  158. #include <stack>
  159. #include <stdlib.h>
  160. #include "fstream"
  161. #include "alg.h"
  162. #include <math.h>
  163.  
  164. using namespace System;
  165. using namespace System::IO;
  166. using namespace std;
  167.  
  168. int main()
  169. {
  170. alg gr;
  171.  
  172. ifstream fin("d:\resC.txt", ios::binary);
  173. int n=10;
  174. char buffer[512];
  175.  
  176. int a[2][512]={};
  177.  
  178. fin.read(buffer, n*2); // считали n байт
  179. int j=0;
  180. for(int i=0;i<n;i++)
  181. {
  182. a[0][i]= (int)buffer[j];
  183. a[1][i]=(int)buffer[j+1];
  184. j=j+2;
  185. }
  186. int p=0;
  187. for(int i=0;i<n;i++)
  188. {
  189. cout«a[0][i]«"#";
  190. cout«a[1][i]«" "«endl;
  191. p=p+2;
  192. }
  193. Point points[256];
  194. for (int i=0;i<n;i++)
  195. {
  196. points[i].x= a[0][i];
  197. points[i].y= a[1][i];
  198.  
  199. }
  200.  
  201. int k = sizeof(points) / sizeof(points[0]);
  202. cout « "The points in the convex hull are: \n";
  203.  
  204. gr.convexHull(points, n);
  205. system("pause");
  206. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top