fork download
copy 
  1. #include <iostream>
  2. #include <sstream>
  3. #include <fstream>
  4. #include <string>
  5. #include <vector>
  6. #include <deque>
  7. #include <queue>
  8. #include <stack>
  9. #include <set>
  10. #include <map>
  11. #include <algorithm>
  12. #include <functional>
  13. #include <utility>
  14. #include <bitset>
  15. #include <cmath>
  16. #include <cstdlib>
  17. #include <ctime>
  18. #include <cstdio>
  19.  
  20. using namespace std;
  21.  
  22. #define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)
  23. #define snuke(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
  24.  
  25. #define N 9
  26. int xx[4],yy[4];
  27. int x[4],y[4];
  28.  
  29. bool is_concyclic(void){
  30. 	int sum = 0;
  31. 	int i;
  32. 	REP(i,3) sum += (x[i] * x[i] + y[i] * y[i]) * (x[(i+1)%3] * y[(i+2)%3] - x[(i+2)%3] * y[(i+1)%3]);
  33. 	return (sum == 0);
  34. }
  35.  
  36. bool is_colinear(void){
  37. 	int i;
  38. 	for(i=1;i<=2;i++) if(x[i] * y[0] != x[0] * y[i]) return false;
  39. 	return true;
  40. }
  41.  
  42. bool is_isosceles(void){
  43. 	int i;
  44.  
  45. 	REP(i,3){
  46. 		int dx1 = x[1] - x[0];
  47. 		int dx2 = x[3] - x[2];
  48. 		int dy1 = y[1] - y[0];
  49. 		int dy2 = y[3] - y[2];
  50.  
  51. 		if(dx1 * dy2 == dx2 * dy1 && (dx1 == 0 || dy1 == 0 || dx1 == dy1 || dx1 == -dy1)) return true;
  52.  
  53. 		int tmp = x[1]; x[1] = x[2]; x[2] = x[0]; x[0] = tmp;
  54. 		tmp = y[1]; y[1] = y[2]; y[2] = y[0]; y[0] = tmp;
  55. 	}
  56.  
  57. 	return false;
  58. }
  59.  
  60. bool is_octagon(void){
  61. 	int i;
  62. 	bool ans = false;
  63.  
  64. 	REP(i,4){
  65. 		x[i] *= 2;
  66. 		y[i] *= 2;
  67. 	}
  68.  
  69. 	for(int p=-N;p<=N;p++) for(int q=-N;q<=N;q++){
  70. 		bool good = true;
  71.  
  72. 		REP(i,4){
  73. 			int dx = abs(p - x[i]);
  74. 			int dy = abs(q - y[i]);
  75. 			if(min(abs(dx), abs(dy)) != min(abs(p), abs(q)) || max(abs(dx), abs(dy)) != max(abs(p), abs(q))) good = false;
  76. 		}
  77.  
  78. 		if(good) return true;
  79. 	}
  80.  
  81. 	REP(i,4){
  82. 		x[i] /= 2;
  83. 		y[i] /= 2;
  84. 	}
  85.  
  86. 	return ans;
  87. }
  88.  
  89. int get_x(int a, int b, int c, int d){
  90. 	return d * (a * a + b * b) - b * (c * c + d * d);
  91. }
  92.  
  93. string itos(int x){
  94. 	stringstream ss;
  95. 	ss << x;
  96. 	return ss.str();
  97. }
  98.  
  99. string get_greek(int p){
  100. 	if(p == 5) return "α";
  101. 	if(p == 13) return "β";
  102. 	if(p == 17) return "γ";
  103. 	if(p == 29) return "δ";
  104. 	return "?";
  105. }
  106.  
  107. int gcd(int x, int y){
  108. 	return x ? gcd(y%x, x) : y;
  109. }
  110.  
  111. string get_equation(int a, int b, int c, int d){ // three points: (0, 0), (a, b), (c, d)
  112. 	int f = 2 * (a * d - b * c);
  113. 	int x = get_x(a, b, c, d);
  114. 	int y = -get_x(b, a, d, c);
  115.  
  116. 	f = abs(f);
  117. 	x = abs(x);
  118. 	y = abs(y);
  119.  
  120. 	int g = gcd(f, gcd(x, y));
  121. 	f /= g;
  122. 	x /= g;
  123. 	y /= g;
  124.  
  125. 	int r = x * x + y * y;
  126. 	x %= f;
  127. 	y %= f;
  128. 	x = min(x, f - x);
  129. 	y = min(y, f - y);
  130. 	if(x > y) swap(x, y);
  131.  
  132. 	string ans;
  133. 	int coef = 1;
  134. 	bool dash = false;
  135.  
  136. 	for(int p=2;p<=r;p++) if(r % p == 0){
  137. 		int cnt = 0;
  138. 		while(r % p == 0){
  139. 			r /= p;
  140. 			cnt++;
  141. 		}
  142.  
  143. 		if(p % 4 != 1){
  144. 			while(cnt >= 2){
  145. 				cnt -= 2;
  146. 				coef *= p;
  147. 			}
  148. 		}
  149.  
  150. 		if(p == 2){
  151. 			if(cnt > 0) dash = true;
  152. 			continue;
  153. 		}
  154.  
  155. 		if(cnt > 0) ans += get_greek(p);
  156. 		if(cnt > 1) ans += "^" + itos(cnt);
  157. 	}
  158.  
  159. 	if(coef > 1) ans = itos(coef) + ans;
  160.  
  161. 	if(dash) ans = ans + '\'';
  162.  
  163. 	if(f > 1){
  164. 		ans += '(';
  165. 		ans += itos(x);
  166. 		ans += ',';
  167. 		ans += itos(y);
  168. 		ans += ")/";
  169. 		ans += itos(f);
  170. 	}
  171.  
  172. 	return ans;
  173. }
  174.  
  175. int unconcyclic;
  176. int colinear;
  177. int isosceles;
  178. int octagon;
  179. map <string, int> mp;
  180.  
  181. void check(void){
  182. 	if(!is_concyclic()){
  183. 		unconcyclic++;
  184. 	} else if(is_colinear()){
  185. 		colinear++;
  186. 	} else if(is_isosceles()){
  187. 		isosceles++;
  188. 	} else if(is_octagon()){
  189. 		octagon++;
  190. 	} else {
  191. 		string s = get_equation(xx[1] - xx[0], yy[1] - yy[0], xx[2] - xx[0], yy[2] - yy[0]);
  192. 		mp[s]++;
  193. 	}
  194. }
  195.  
  196. void dfs(int pos, int hash){
  197. 	if(pos == 4){
  198. 		int i;
  199. 		REP(i,4){
  200. 			x[i] = xx[i] - xx[3];
  201. 			y[i] = yy[i] - yy[3];
  202. 		}
  203. 		check();
  204. 	} else {
  205. 		for(int h=hash+1;h<N*N;h++){
  206. 			xx[pos] = h / N;
  207. 			yy[pos] = h % N;
  208. 			dfs(pos + 1, h);
  209. 		}
  210. 	}
  211. }
  212.  
  213. int main(void){
  214. 	dfs(0, -1);
  215.  
  216. 	cout << "unconcyclic: " << unconcyclic << endl;
  217. 	cout << "colinear: " << colinear << endl;
  218. 	cout << "isosceles: " << isosceles << endl;
  219. 	cout << "octagon: " << octagon << endl;
  220.  
  221. 	vector <pair <int, string> > v;
  222. 	snuke(mp,itr) v.push_back(make_pair(-(itr->second), (itr->first)));
  223. 	sort(v.begin(),v.end());
  224.  
  225. 	int i;
  226. 	REP(i,v.size()) cout << v[i].second << ": " << -v[i].first << endl;
  227.  
  228. 	return 0;
  229. }
  230.  
Success #stdin #stdout 0.08s 15256KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
unconcyclic: 1634588
colinear: 3156
isosceles: 9888
octagon: 8300
α^2'(1,1)/2: 4536
αβ'(1,1)/2: 640
αβ(0,1)/2: 624
α^2(0,1)/2: 560
αγ'(1,1)/2: 352
α^2: 344
α^2β'(1,1)/6: 160
αγ(0,1)/2: 160
αδ'(1,1)/2: 96
α^2β'(1,1)/2: 80
α^2β(1,2)/4: 72
αβγ'(1,5)/14: 72
αβ: 40
α^2': 32
α^3(0,1)/2: 24
α^2γ(0,1)/4: 16
https://ideone.com/zL0R92
language:
C++ (gcc 8.3)
created:
5 years ago
visibility:
public

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!