fork download
copy 
  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
comments (?)
stdin
copy 
2
5
1 1
2 2
3 3
4 1
6 4
5
0 0
3 1
5 1
5 -1
1 3
stdout
copy 
3
4
https://ideone.com/ahuhnB
language:
C++14 (gcc 8.3)
created:
6 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!