fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define Foreach(i, c) for(__typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
  4. #define For(i,a,b) for(int (i)=(a);(i) < (b); ++(i))
  5. #define rof(i,a,b) for(int (i)=(a);(i) > (b); --(i))
  6. #define rep(i, c)  for(auto &(i) : (c))
  7. #define x     first
  8. #define y     second
  9. #define pb  push_back
  10. #define PB  pop_back()
  11. #define iOS  ios_base::sync_with_stdio(false)
  12. #define sqr(a)  (((a) * (a)))
  13. #define all(a)  a.begin() , a.end()
  14. #define error(x) cerr << #x << " = " << (x) <<endl
  15. #define Error(a,b) cerr<<"( "<<#a<<" , "<<#b<<" ) = ( "<<(a)<<" , "<<(b)<<" )\n";
  16. #define errop(a) cerr<<#a<<" = ( "<<((a).x)<<" , "<<((a).y)<<" )\n";
  17. #define coud(a,b) cout<<fixed << setprecision((b)) << (a)
  18. #define L(x)  ((x)<<1)
  19. #define R(x)  (((x)<<1)+1)
  20. #define umap  unordered_map
  21. //#define max(x,y)  ((x) > (y) ? (x) : (y))
  22. #define double long double
  23. typedef long long ll;
  24. typedef pair<int,int>pii;
  25. typedef vector<int> vi;
  26. //typedef complex<double> point;
  27. const int maxn = 1e6 + 100;
  28. map <pii, vi> mp;
  29. const double eps = 1e-22;
  30. struct point{
  31. 	int X,Y;
  32. 	double x,y;
  33. 	point(){
  34. 		X = Y = x = y = .0;
  35. 	}
  36. 	point(double a,double b){
  37. 		x = a, y = b;
  38. 	}
  39. 	inline void init(int a,int b){
  40. 		X = a, Y = b;
  41. 		x = 1.0 / X;
  42. 		y = 1.0 / Y;
  43. 	}
  44. 	inline double operator * (point p){
  45. 		return x * p.y - y * p.x;
  46. 	}
  47. 	inline point operator - (point p){
  48. 		return point(x - p.x, y - p.y);
  49. 	}
  50. 	inline double dis(point p){
  51. 		return sqr(x - p.x) + sqr(y - p.y);
  52. 	}
  53. 	inline pii PII(){
  54. 		return pii(X, Y);
  55. 	}
  56. };
  57. point o;
  58. point l;
  59. inline bool ocmp(const point &a, const point &b){
  60. 	return make_pair(a.y, a.x) < make_pair(b.y, b.x);
  61. }
  62. inline bool lcmp(const point &a, const point &b){
  63. 	return make_pair(a.x, a.y) < make_pair(b.x, b.y);
  64. }
  65. inline bool scmp(const point &a,const point &b){
  66. 	double cross = ((point)a - o) * ((point)b - o);
  67. 	if(fabs(cross) <= eps)
  68. 		return o.dis(a) < o.dis(b);
  69. 	return cross < eps;
  70. }
  71. vector<point> v;
  72. vector<point> hull;
  73. int n;
  74. int main(){
  75.     iOS;
  76. 	cin >> n;
  77. 	For(i,0,n){
  78. 		int a,b;
  79. 		cin >> a >> b;
  80. 		mp[{a, b}].pb(i + 1);
  81. 	}
  82. 	if(mp.size() == 1){
  83. 		For(i,1,n+1)
  84. 			cout << i << ' ';
  85. 		cout << endl;
  86. 		return 0;
  87. 	}
  88. 	Foreach(q, mp){
  89. 		pii p = q->x;
  90. 		int x = p.x, y = p.y;
  91. 		point P;
  92. 		P.init(x, y);
  93. 		v.pb(P);
  94. 	}
  95. 	o = *min_element(all(v), ocmp);
  96. 	l = *min_element(all(v), lcmp);
  97. 	if(o.PII() == l.PII()){
  98. 		rep(a, mp[o.PII()])
  99. 			cout << a << ' ';
  100. 		cout << endl;
  101. 		return 0;
  102. 	}
  103. 	sort(all(v), scmp);
  104. 	int po = 2;
  105. 	For(i,0,2)
  106. 		hull.pb(v[i]);
  107. 	vi ans;
  108. 	while(po < v.size() && hull.back().PII() != l.PII()){
  109. 		while(hull.size() > 1 && (hull[hull.size()-1] - hull[hull.size()-2]) * (v[po] - hull[hull.size()-2]) > eps)
  110. 			hull.PB;
  111. 		hull.pb(v[po++]);
  112. 	}
  113. 	rep(p, hull)
  114. 		rep(a, mp[p.PII()])
  115. 			ans.pb(a);
  116. 	sort(all(ans));
  117. 	rep(a, ans)
  118. 		cout << a << ' ';
  119. 	cout << endl;
  120.  
  121. }
  122.  
Runtime error #stdin #stdout 0s 3244KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/pcc5xc
language:
C++14 (gcc 8.3)
created:
9 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!