fork download
copy 
  1. #include<iostream>
  2. #include<vector>
  3. #include<string>
  4. #include<algorithm>
  5. #include<cmath>
  6. //#include"Point.h"
  7.  
  8. using namespace std;
  9.  
  10. #define TWO_PI (2*M_PI)
  11.  
  12. struct Point{
  13. 	char label;//for gnuplot.
  14. 	int index;//rank. sort by heading.
  15. 	double x, y;//coordinate.
  16. 	double theta;//against base poit.
  17.  
  18. 	double heading(const Point& other){
  19. 		return atan2(y - this->y, x - this->x);
  20. 	}
  21. 	friend ostream& operator<<(ostream& os, const Point& self);
  22. };
  23. ostream& operator<<(ostream& os, const Point& self){
  24. 	os << self.label << ":" << "(" << self.x << ", " << self.y << ")" << ", " << self.index << ", " << self.theta;
  25. 	return os;
  26. }
  27.  
  28. void show(vector<Point>& ps){
  29. 	for(int i=0; i<ps.size(); i++){
  30. 		cout << ps[i] << endl;
  31. 	}
  32. }
  33. bool cmp_coord(const Point& a, const Point& b){
  34. 	return a.y < b.y ? a.y < b.y : a.x < b.x;
  35. }
  36. void func_index(vector<Point>& ps){
  37. 	for(int i=0; i<ps.size(); i++){
  38. 		ps[i].index = i;
  39. 	}
  40. }
  41.  
  42.  
  43. //base point（ps[0]）に対して角度順に整列されているかどうかを表示（可視化）するためのgpファイルを出力する。
  44. void show_gp(vector<Point>& ps, char base[]){
  45. 	cout << "set size square" << endl;
  46. 	cout << "set nokey" << endl;//凡例を消す
  47.  
  48. 	for(int i=0; i<ps.size(); i++){
  49. 		printf("set label %d at %lf,%lf \"%c %d\"\n", i+1, ps[i].x, ps[i].y, ps[i].label, ps[i].index);
  50. 	}
  51.  
  52. 	printf("plot \"%s_gnuplot.dat\"\n", base);
  53. }
  54.  
  55. //base point（ps[0]）に対する角度（偏角）を求める。また、それ自身（ps[0]）同士の偏角も求めているものの、ゼロ除算は（どういうわけか）起こらない。
  56. void func_theta(vector<Point>& ps, const Point base){
  57. 	for(int i=0; i<ps.size(); i++){
  58. 		ps[i].theta = atan2(ps[i].y - base.y, ps[i].x - base.x);
  59. 	}
  60. }
  61. bool cmp_theta(const Point& a, const Point& b){
  62. 	return a.theta < b.theta;
  63. }
  64. bool is_counter_clock_wise(const Point& a, const Point& b, const Point& c){
  65. 	//return (b.x-a.x)*(c.y-a.y) - (b.x-a.y)*(c.x-a.x) < 0;
  66. 	//return (b.x-a.x)*(c.y-a.y) - (a.x-b.y)*(c.x-b.x) < 0;
  67. 	Point v;
  68. 	v.x = a.x - b.x;
  69. 	v.y = a.y - b.y;
  70.  
  71. 	Point w;
  72. 	w.x = c.x - b.x;
  73. 	w.y = c.y - b.y;
  74.  
  75. 	return v.x*w.y - w.x*v.y > 0;
  76. }
  77. void check_ccw(vector<Point>& ch, vector<Point>& internal){
  78. 	if(is_counter_clock_wise(ch[ch.size()-1], ch[ch.size()-2], ch[ch.size()-3])){
  79. 		return;
  80. 	}
  81.  
  82. 	internal.push_back(ch[ch.size()-2]);
  83. 	ch.erase(ch.end()-2);
  84. 	return check_ccw(ch, internal);
  85. }
  86. vector<Point> get_convex_hull(vector<Point>& ps, vector<Point>& internal){
  87. 	vector<Point> ch;
  88.  
  89. 	for(int i=0; i<3; i++){
  90. 		ch.push_back(ps[0]);
  91. 		ps.erase(ps.begin());
  92. 	}
  93.  
  94. 	while(!ps.empty()){
  95. 		ch.push_back(ps[0]);
  96. 		ps.erase(ps.begin());
  97. 		check_ccw(ch, internal);
  98. 	}
  99.  
  100. 	return ch;
  101. }
  102. void output(vector<Point>& ps, char fn[], bool is_closed){
  103. 	FILE* fp = fopen(fn, "w");
  104. 	for(int i=0; i<ps.size(); i++){
  105. 		fprintf(fp, "%lf %lf\n", ps[i].x, ps[i].y);
  106. 	}
  107. 	if(is_closed){
  108. 		fprintf(fp, "%lf %lf\n", ps[0].x, ps[0].y);
  109. 	}
  110. 	fclose(fp);
  111. }
  112. void show_ch(vector<Point>& ch, vector<Point>& internal, char base[], bool is_png){
  113. 	if(is_png){
  114. 		printf("set terminal png\n");
  115. 		printf("set output \"%s.png\"\n", base);
  116. 	}
  117.  
  118. 	cout << "set size square" << endl;
  119. 	cout << "set nokey" << endl;//凡例を消す
  120.  
  121. 	for(int i=0; i<internal.size(); i++){
  122. 		printf("set label %d at %lf,%lf \"%c %d\"\n", i+1, internal[i].x, internal[i].y, internal[i].label, internal[i].index);
  123. 	}
  124. 	for(int j=internal.size()+1, i=0; i<ch.size(); i++, j++){
  125. 		printf("set label %d at %lf,%lf \"%c %d\"\n", j+1, ch[i].x, ch[i].y, ch[i].label, ch[i].index);
  126. 	}
  127.  
  128. 	char fn_int[256];
  129. 	sprintf(fn_int, "%s_internal.dat", base);
  130. 	char fn_ch[256];
  131. 	sprintf(fn_ch, "%s_convex_hull.dat", base);
  132.  
  133. 	output(internal, fn_int, false);
  134. 	output(ch, fn_ch, true);
  135.  
  136. 	printf("plot \"%s\"\n", fn_int);
  137. 	printf("plot \"%s\" with lines\n", fn_ch);
  138. }
  139. int main(int argc, char* args[]){
  140. 	////コマンドライン引数
  141. 	if(argc != 2){
  142. 		fprintf(stderr, "arg error, argc=%d\n", argc);
  143. 		exit(1);
  144. 	}
  145. 	//graham [basename]
  146. 	//graham data9
  147.  
  148. 	char base[256];
  149. 	strcpy(base, args[1]);
  150.  
  151.  
  152. 	////読み込み
  153. 	int N;
  154. 	cin >> N;
  155.  
  156. 	vector<Point> ps;
  157.  
  158. 	for(int i=0; i<N; i++){
  159. 		Point temp;
  160. 		cin >> temp.label >> temp.x >> temp.y;
  161. 		temp.index = -1;
  162. 		temp.theta = 0;
  163. 		ps.push_back(temp);
  164. 	}
  165. 	//show(ps);//check, ok
  166. 	//exit(0);//check, ok
  167.  
  168.  
  169. 	////左下の探査（並び換え）
  170. 	sort(ps.begin(), ps.end(), cmp_coord);
  171. 	//show(ps);//check, ok
  172. 	//exit(0);//check, ok
  173.  
  174.  
  175. 	////角度による並び換え
  176. 	func_theta(ps, ps[0]);
  177. 	sort(ps.begin(), ps.end(), cmp_theta);
  178. 	func_index(ps);
  179. 	//show(ps);//check, ok
  180. 	//show_gp(ps, base);//check, ok
  181.  
  182.  
  183. 	////凸包（convex hull）を求める
  184. 	vector<Point> internal;
  185. 	vector<Point> ch = get_convex_hull(ps, internal);
  186. 	//show(ch);//check, ok
  187. 	show_ch(ch, internal, base, false);
  188.  
  189. 	return 0;
  190. }
  191.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp: In function ‘int main(int, char**)’:
prog.cpp:149:2: error: ‘strcpy’ was not declared in this scope
  strcpy(base, args[1]);
  ^~~~~~
prog.cpp:149:2: note: ‘strcpy’ is defined in header ‘<cstring>’; did you forget to ‘#include <cstring>’?
prog.cpp:6:1:
+#include <cstring>
 //#include"Point.h"
prog.cpp:149:2:
  strcpy(base, args[1]);
  ^~~~~~
stdout
copy 
Standard output is empty
https://ideone.com/t9u83o
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!