fork(2) 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. #define int ll
  25. typedef pair<ll,ll>pii;
  26. typedef vector<int> vi;
  27. //typedef complex<double> point;
  28. const int maxn = 1e6 + 100;
  29. map <pii, vi> mp;
  30. struct point{
  31. ll x,y;
  32. point(){
  33. x = y = 0;
  34. }
  35. point(ll a,ll b){
  36. x = a, y = b;
  37. }
  38. inline void init(ll a,ll b){
  39. x = a, y = b;
  40. }
  41. inline point operator - (point p){
  42. return point(x - p.x, y - p.y);
  43. }
  44. inline ll dis(point p){
  45. return sqr(x - p.x) + sqr(y - p.y);
  46. }
  47. inline pii PII(){
  48. return pii(x, y);
  49. }
  50. };
  51. inline ll CROSS(point o, point a,point b){
  52. return (a.y * b.x * o.x * o.y - a.y * o.x * b.x * b.y - o.y * b.x * a.x * a.y + a.x * b.x * a.y * b.y) -
  53. (a.x * b.y * o.x * o.y - a.x * o.y * b.x * b.y - o.x * b.y * a.x * a.y + a.x * b.x * a.y * b.y);
  54. }
  55. point o;
  56. point l;
  57. inline bool ocmp(const point &a, const point &b){
  58. return make_pair(a.y, a.x) > make_pair(b.y, b.x);
  59. }
  60. inline bool lcmp(const point &a, const point &b){
  61. return make_pair(a.x, a.y) > make_pair(b.x, b.y);
  62. }
  63. inline bool scmp(const point &a,const point &b){
  64. ll cross = CROSS(o, a, b);
  65. if(!cross)
  66. return o.dis(a) < o.dis(b);
  67. return cross < 0;
  68. }
  69. vector<point> v;
  70. vector<point> hull;
  71. int n;
  72. main(){
  73. iOS;
  74. cin >> n;
  75. For(i,0,n){
  76. int a,b;
  77. cin >> a >> b;
  78. mp[{a, b}].pb(i + 1);
  79. }
  80. if(mp.size() == 1){
  81. For(i,1,n+1)
  82. cout << i << ' ';
  83. cout << endl;
  84. return 0;
  85. }
  86. Foreach(q, mp){
  87. pii p = q->x;
  88. int x = p.x, y = p.y;
  89. point P;
  90. P.init(x, y);
  91. v.pb(P);
  92. }
  93. o = *min_element(all(v), ocmp);
  94. l = *min_element(all(v), lcmp);
  95. if(o.PII() == l.PII()){
  96. rep(a, mp[o.PII()])
  97. cout << a << ' ';
  98. cout << endl;
  99. return 0;
  100. }
  101. sort(all(v), scmp);
  102. int po = 2;
  103. For(i,0,2)
  104. hull.pb(v[i]);
  105. vi ans;
  106. while(po < v.size() && hull.back().PII() != l.PII()){
  107. while(hull.size() > 1 && CROSS(hull[hull.size()-2], hull[hull.size()-1], v[po]) > 0LL)
  108. hull.PB;
  109. hull.pb(v[po++]);
  110. }
  111. rep(p, hull)
  112. rep(a, mp[p.PII()])
  113. ans.pb(a);
  114. sort(all(ans));
  115. rep(a, ans)
  116. cout << a << ' ';
  117. cout << endl;
  118.  
  119. }
  120.  
Runtime error #stdin #stdout 0s 3244KB
stdin
Standard input is empty
stdout
Standard output is empty