• API
• FAQ
• Tools
• Archive
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.

Top