fork download
copy 
  1. #include <bits/extc++.h>
  2. #include <bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. #define int int64_t
  7.  
  8. typedef int64_t ftype;
  9. typedef complex<ftype> point;
  10. #define x real
  11. #define y imag
  12.  
  13. ftype dot(point a, point b)
  14. {
  15. 	return (conj(a) * b).x();
  16. }
  17.  
  18. ftype cross(point a, point b)
  19. {
  20. 	return (conj(a) * b).y();
  21. }
  22.  
  23. const int mod = 998244353;
  24.  
  25. void add_mod(int &a, int b)
  26. {
  27. 	a += b;
  28. 	while(a >= mod)
  29. 		a -= mod;
  30. 	while(a < 0)
  31. 		a += mod;
  32. }
  33.  
  34. signed main()
  35. {
  36. 	//freopen("input.txt", "r", stdin);
  37. 	ios::sync_with_stdio(0);
  38. 	cin.tie(0);
  39. 	int n;
  40. 	cin >> n;
  41. 	point r[n];
  42. 	for(int i = 0; i < n; i++)
  43. 	{
  44. 		int x, y;
  45. 		cin >> x >> y;
  46. 		r[i] = {x, y};
  47. 	}
  48. 	int ans = 0;
  49. 	for(int s = 0; s < n; s++)
  50. 	{
  51. 		point o = r[s];
  52. 		vector<point> pts;
  53. 		for(int i = 0; i < n; i++)
  54. 			if(r[i].y() > o.y() || r[i].y() == o.y() && r[i].x() > o.x())
  55. 				pts.push_back(r[i]);
  56. 		sort(begin(pts), end(pts), [&](point a, point b)
  57. 			{return cross(a - o, b - o) < 0 || cross(a - o, b - o) == 0 && norm(a) < norm(b);});
  58. 		int m = pts.size();
  59. 		int dp[m][m];
  60. 		for(int i = 0; i < m; i++)
  61. 			for(int j = 0; j < m; j++)
  62. 				dp[i][j] = 0;
  63. 		for(int r = 0; r < m; r++)
  64. 			for(int l = 0; l < r; l++)
  65. 			{
  66. 				if(cross(pts[r] - o, pts[l] - o) == 0)
  67. 					continue;
  68. 				dp[l][r] = 1;
  69. 				for(int p = 0; p < l; p++)
  70. 					if(cross(pts[p] - o, pts[l] - o) == 0)
  71. 						add_mod(dp[l][r], dp[l][r]);
  72. 				for(int p = 0; p < l; p++)
  73. 					if(cross(pts[l] - pts[p], pts[r] - pts[p]) < 0)
  74. 						add_mod(dp[l][r], dp[p][l]);
  75. 				for(int p = l + 1; p < r; p++)
  76. 					if(cross(pts[r] - pts[l], pts[p] - pts[l]) <= 0)
  77. 						add_mod(dp[l][r], dp[l][r]);
  78. 				add_mod(ans, dp[l][r]);
  79. 			}
  80. 	}
  81. 	cout << ans << endl;
  82.     return 0;
  83. }
  84.  
Runtime error #stdin #stdout 0s 15248KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/pIn0Zm
language:
C++14 (gcc 8.3)
created:
7 years 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!