fork(7) download
copy 
  1. #include <iostream>
  2. #include <cmath>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <cstring>
  6. #include <deque>
  7. #include <time.h>
  8. #include <stack>
  9. #include <stdio.h>
  10. #include <map>
  11. #include <set>
  12. #include <string>
  13. #include <fstream>
  14. #include <queue>
  15. #include <unordered_map>
  16. #define mp make_pair
  17. #define pb push_back
  18. #define PI 3.14159265358979323846
  19. #define MOD 1000000007
  20. #define INF ((ll)1e+15)
  21. #define x1 fldgjdflgjhrthrl
  22. #define x2 fldgjdflgrtyrtyjl
  23. #define y1 fldggfhfghjdflgjl
  24. #define y2 ffgfldgjdflgjl
  25. typedef long long ll;
  26. using namespace std;
  27. int i,j,n,m,x[3005],y[3005],a[4500000],b[20005][205];
  28. unordered_map <ll, int> f;
  29. unordered_map <ll, int>::iterator itr;
  30. ll Abs(int a)
  31. {
  32. 	return a>0?a:-a;
  33. }
  34. ll gcd(int a, int b)
  35. {
  36. 	if (b == 0)
  37. 	   return a;
  38. 	return gcd(b,a%b);
  39. }
  40. int main()
  41. {
  42. 	for (i = 1; i <= 20000; i++)
  43.         for (j = 1; j <= 200; j++)
  44.             b[i][j] = gcd(i,j);
  45. 	for (i = 1; i <= 20000; i++)
  46. 		b[i][0] = i;
  47. 	for (i = 1; i <= 200; i++)
  48. 		b[0][i] = i;
  49.  	cin >> n;
  50.  	for (i = 2; i <= 2000; i++)
  51. 		a[i*i-i] = i;
  52.  	for (i = 0; i < n; i++)
  53. 		cin >> x[i] >> y[i];
  54. 	for (i = 0; i < n; i++)
  55. 	{
  56. 		for (j = 0; j < n; j++)
  57. 		if (i != j)
  58. 		{
  59. 			int kc = y[j] - y[i];
  60. 			int kz = x[j] - x[i];
  61. 			int bc = y[i]*(x[j] - x[i]) - x[i]*(y[j]-y[i]);
  62. 			int bz = x[j] - x[i];
  63. 			if (kz != 0)
  64. 			{
  65. 			int tmp = b[Abs(kc)][Abs(kz)];
  66. 			kc /= tmp; kz /= tmp;
  67. 			if (kc < 0)
  68. 			   kc = -kc, kz = -kz;
  69. 			if (kc == 0)
  70. 			   kz = 1;
  71.             tmp = b[Abs(bc)][Abs(bz)];
  72. 			bc /= tmp; bz /= tmp;
  73. 			if (bc < 0)
  74. 			   bc = -bc, bz = -bz;
  75. 			if (bc == 0)
  76. 			   bz = 1;
  77.             }
  78.             else
  79.             kc = bc = x[i];
  80.             ll hsh = bc*27000000000LL + bz*9000000LL + kc*300 + kz;
  81. 				f[hsh]+=2;
  82. 		}
  83. 	}
  84. 	ll ans = ((ll)n*(n-1)*(n-2))/6;
  85. 	for (itr = f.begin(); itr != f.end(); itr++)
  86. 	{
  87. 		int tmp = (*itr).second;
  88. 		tmp = a[tmp/2];
  89. 		ans -= ((ll)tmp*(tmp-1)*(tmp-2))/6;
  90. 	}
  91. 	cout << ans << endl;
  92. 	return 0;
  93. }
Success #stdin #stdout 0.31s 36856KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/MTrDB8
language:
C++14 (gcc 8.3)
created:
9 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!