fork(1) download
  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
stdin
Standard input is empty
stdout
Standard output is empty