fork download
  1. #include <set>
  2. #include <map>
  3. #include <algorithm>
  4. #include <cmath>
  5. #include <vector>
  6. #include <cstdio>
  7. #include <cstring>
  8. #include <iostream>
  9. #include <queue>
  10. #include <sstream>
  11. #include <cassert>
  12. using namespace std;
  13.  
  14. typedef long long ll;
  15.  
  16. const ll INF=1000000000LL*1000000000LL;
  17.  
  18. struct point
  19. {
  20. ll x,y;
  21. point(ll x=0, ll y=0):x(x),y(y){}
  22. point operator+(const point& p) const
  23. {
  24. return point(x+p.x, y+p.y);
  25. }
  26. point operator-(const point& p) const
  27. {
  28. return point(x-p.x, y-p.y);
  29. }
  30. point rot() const
  31. {
  32. return point(y,-x);
  33. }
  34. ll inner(const point& p) const
  35. {
  36. return x*p.x + y*p.y;
  37. }
  38. ll cross(const point& p) const
  39. {
  40. return x*p.y - y*p.x;
  41. }
  42. ll norm2() const
  43. {
  44. return x*x+y*y;
  45. }
  46. //lexicographical
  47. bool cmp(const point& p) const
  48. {
  49. if(y!=p.y) return y<p.y;
  50. return x<p.x;
  51. }
  52.  
  53. //polar
  54. bool operator<(const point& p) const
  55. {
  56. bool down1=this->cmp(point(0,0));
  57. bool down2=p.cmp(point(0,0));
  58. if(down1!=down2)
  59. return down1>down2;
  60. return this->cross(p)>0;
  61. }
  62. bool operator==(const point& p) const
  63. {
  64. return this->cross(p)==0 && this->inner(p)>0;
  65. }
  66. bool operator!=(const point& p) const
  67. {
  68. return !((*this)==p);
  69. }
  70. };
  71.  
  72. struct Event
  73. {
  74. point p;
  75. // 0 - add
  76. // 1 - query
  77. // 2 - rem
  78. int type;
  79. Event(point p=point(), int type=0):
  80. p(p),
  81. type(type)
  82. {}
  83. bool operator<(const Event& ev) const
  84. {
  85. if(p!=ev.p)
  86. return p<ev.p;
  87. return type<ev.type;
  88. }
  89. };
  90.  
  91. int main()
  92. {
  93. int T;
  94. scanf("%d",&T);
  95. while(T--)
  96. {
  97. int n;
  98. scanf("%d",&n);
  99. vector<point> p(n);
  100. set<pair<int,int> > used;
  101. for(int i=0;i<n;i++)
  102. scanf("%lld%lld",&p[i].x, &p[i].y);
  103.  
  104. ll res=ll(n)*(n-1)*(n-2)/6;
  105. ll bad=0;
  106.  
  107. vector<point> v;
  108. vector<Event> ev;
  109. for(int i=0;i<n;i++)
  110. {
  111. v.clear();
  112. ev.clear();
  113.  
  114. for(int j=0;j<n;j++)
  115. if(i!=j)
  116. v.push_back(p[j]-p[i]);
  117.  
  118. point sample(-2000000001,1);
  119. int cnt=0;
  120. for(int j=0;j+1<n;j++)
  121. {
  122. point c=v[j];
  123. ev.push_back(Event(c, 1));
  124. point A, B;
  125. A=c.rot();
  126. B=A.rot().rot();
  127. if(B<A)
  128. swap(A,B);
  129. bool present=v[j].inner(sample)<=0;
  130. if(present)
  131. {
  132. cnt++;
  133. ev.push_back(Event(A,2));
  134. ev.push_back(Event(B,0));
  135. }
  136. else
  137. {
  138. ev.push_back(Event(A,0));
  139. ev.push_back(Event(B,2));
  140. }
  141. }
  142.  
  143. sort(ev.begin(), ev.end());
  144. for(const Event & e: ev)
  145. {
  146. if(e.type==1)
  147. bad+=cnt;
  148. else if(e.type==0)
  149. cnt++;
  150. else
  151. cnt--;
  152. }
  153. }
  154. res-=bad/2;
  155. cout<<res<<endl;
  156. }
  157. return 0;
  158. }
  159.  
Success #stdin #stdout 0s 15232KB
stdin
2
5
1 1
2 2
3 3
4 1
6 4
5
0 0
3 1
5 1
5 -1
1 3
stdout
3
4