fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int n;
  4. vector<pair<double ,double> > points,equations;
  5. vector<double> infinite_slope;
  6. //points will contain x-cordinate and y-cordinate
  7. //equations will contain m & c [ y= m*x +c ]
  8. //infinite slope cannot be stored in equations without making some valid assumptions,
  9. //so we are storing the y-coordinate in another vector
  10. #define LL long long int
  11. void get_input()
  12. {
  13. 	cin>>n;
  14. 	points.resize(n);
  15. 	int i;
  16. 	for(i=0;i<n;i++)
  17. 		cin>>points[i].first>>points[i].second;
  18. }	
  19. void make_equations()
  20. {
  21. 	//converts points to equations
  22. 	int i,j,count;
  23. 	//number of equations will be nC2 i.e. n*(n-1)/2
  24. 	count=n*(n-1)/2;
  25. 	for(i=0;i<n;i++)
  26. 	{
  27. 		for(j=i+1;j<n;j++)
  28. 		{
  29. 			double x1,y1,x2,y2,m,c;
  30. 			x1=points[i].first;
  31. 			y1=points[i].second;
  32. 			x2=points[j].first;
  33. 			y2=points[j].second;
  34. 			if(x1==x2)
  35. 			{
  36. 				infinite_slope.push_back(y1);
  37. 			}
  38. 			else
  39. 			{
  40. 				m=(y2-y1)/(x2-x1);
  41. 				c=y1-m*x1;
  42. 				equations.push_back(make_pair(m,c));
  43. 			}
  44. 		}
  45. 	}
  46. }
  47.  
  48. LL get_n_from_nC2(LL x)
  49. {
  50. 	//for a given nC2, calculates value of n
  51. 	LL ans=(LL)sqrt(2*x);
  52. 	ans++;
  53. 	return ans;
  54. }
  55. LL calculate(LL x)
  56. {
  57. 	//for a given nC2 calculates value of nC3
  58. 	LL count=get_n_from_nC2(x);
  59. 	LL ans=(count*(count-1)*(count-2))/6;
  60. 	return ans;
  61. }
  62. LL number_of_triangles()
  63. {
  64. 	make_equations();
  65. 	sort(equations.begin(),equations.end());
  66. 	sort(infinite_slope.begin(),infinite_slope.end());
  67. 	/*
  68. 	Total Triangles possible -> nC3
  69. 	But all triangles that lie on a straight line have zero areas ,
  70. 	so those need to be subtracted from the total
  71. 	*/
  72. 	LL total=(n*(n-1)*(n-2))/6,count=1;
  73. 	int i;
  74. 	for(i=1;i<equations.size();i++)
  75. 	{
  76. 		if(equations[i].first==equations[i-1].first && equations[i].second==equations[i-1].second)
  77. 			{
  78. 				count++;
  79. 			}
  80. 		else
  81. 			{
  82. 				total-=calculate(count);
  83. 				count=1;
  84. 			}
  85. 	}
  86. 	total-=calculate(count);
  87. 	count=1;
  88. 	for(i=1;i<infinite_slope.size();i++)
  89. 	{
  90. 		if(infinite_slope[i]==infinite_slope[i-1] &&
  91. 		                     infinite_slope[i]==infinite_slope[i-1])
  92. 			{
  93. 				count++;
  94. 			}
  95. 		else
  96. 		{
  97. 				//this count is actuallly nC2 
  98. 				total-=calculate(count);
  99. 				count=1;
  100. 		}
  101. 	}
  102. 	total-=calculate(count);
  103. 	return total;
  104. }
  105. void display_equations()
  106. {
  107. 	cout<<"\n\n  ***\t\t***\n\n Equations -->\n\n";
  108. 	int i;
  109. 	for(i=0;i<equations.size();i++)
  110. 	{
  111. 		cout<<equations[i].first<<"\t"<<equations[i].second<<endl;
  112. 	}
  113.  
  114. }
  115. int main()
  116. {
  117. 	get_input();
  118. 	cout<<number_of_triangles()<<endl;
  119. 	//display_equations();
  120. 	return 0;
  121. }
Success #stdin #stdout 0s 3240KB
comments (?)
stdin
copy 
1
1 1
stdout
copy 
0
https://ideone.com/FoQyfl
language:
C++14 (gcc 8.3)
created:
8 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!