fork download
  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
stdin
1
1 1
stdout
0