fork(1) download
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <vector>
  4. #include <set>
  5. using namespace std;
  6. const int MAX = 200005;
  7. pair<int, int> p[MAX];
  8. vector<pair<int, int> > v;
  9. int a[MAX], b[MAX];
  10. pair<long long, long long> intersect(pair<int, int> a, pair<int, int> b)
  11. {
  12. return make_pair(a.first * (b.second - a.second), a.second * (b.first - a.first));
  13. }
  14. bool cmp(pair<long long, long long> a, pair<long long, long long> b)
  15. {
  16. return (a.first * b.second < a.second * b.first);
  17. }
  18. int main()
  19. {
  20. ios::sync_with_stdio(false);
  21. int n;
  22. cin >> n;
  23. int tn = n;
  24. for (int i = 0; i < n; i++)
  25. {
  26. cin >> p[i].first >> p[i].second;
  27. a[i] = p[i].first;
  28. b[i] = p[i].second;
  29. }
  30. sort(p, p + n);
  31. for (int i = 0; i < n; i++)
  32. {
  33. while (!v.empty() && v.back().second <= p[i].second)
  34. v.pop_back();
  35. v.push_back(p[i]);
  36. }
  37. n = v.size();
  38. for (int i = 0; i < n; i++)
  39. p[i] = v[i];
  40. v.clear();
  41. for (int i = 0; i < n; i++)
  42. {
  43. while (v.size() > 1 && cmp(intersect(p[i], v.back()), intersect(v[v.size() - 2], v.back())))
  44. v.pop_back();
  45. v.push_back(p[i]);
  46. }
  47. set<pair<int, int> > s;
  48. for (int i = 0; i < v.size(); i++)
  49. s.insert(v[i]);
  50. vector<int> ans;
  51. for (int i = 0; i < tn; i++)
  52. if (s.count(make_pair(a[i], b[i])))
  53. ans.push_back(i + 1);
  54. for (int i = 0; i < ans.size(); i++)
  55. cout << ans[i] << " ";
  56. cout << endl;
  57. return 0;
  58. }
Runtime error #stdin #stdout 0s 6360KB
stdin
Standard input is empty
stdout
Standard output is empty