fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define pb push_back
  5. #define mp make_pair
  6. #define f1 first
  7. #define s2 second
  8.  
  9. #define fastio ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
  10. #define debug(x...) cerr << "[" << #x << "]: " << x << "\n";
  11.  
  12. using ll = long long;
  13. using ld = long double;
  14. using ii = pair<int, int>;
  15. using pl = pair<ll, ll>;
  16.  
  17. ld const PI = 4*atan((ld)1);
  18.  
  19. struct Point
  20. {
  21. 	ll x, y;
  22. 	Point() : x(0), y(0) {}
  23. 	Point(int p, int q) : x(p), y(q) {}
  24.  
  25. 	string out() const
  26. 	{
  27. 		string res = "";
  28. 		res += "(";
  29. 		res += to_string(x);
  30. 		res += ",";
  31. 		res += to_string(y);
  32. 		res += ")";
  33. 		return res;
  34. 	}
  35.  
  36. 	bool operator<(Point const &other) const { return x < other.x || (x == other.x && y < other.y); }
  37. 	bool operator==(Point const &other) const { return x == other.x && y == other.y; }
  38. };
  39.  
  40. int orientation(Point a, Point b, Point c)
  41. {
  42. 	int o = (a.y - b.y) * (b.x - c.x) - (a.x - b.x) * (b.y - c.y);
  43.  
  44. 	if (o == 0)
  45. 		return 0;
  46. 	return o > 0 ? -1 : 1; // CW : CCW
  47. }
  48.  
  49. int main()
  50. {
  51. 	fastio;
  52.  
  53. 	int n;
  54. 	cin >> n;
  55.  
  56. 	vector<Point> v(n);
  57. 	for (Point &p : v)
  58. 		cin >> p.x >> p.y;
  59.  
  60. 	sort(v.begin(), v.end());
  61. 	for (int i = 0; i < v.size(); ++i)
  62. 		cout << v[i].x << "," << v[i].y << " -- ";
  63. 	return 0;
  64. 	/*
  65. 	cerr << '\n';
  66.  
  67. 	sort(v.begin(), v.end(), [&](Point const &p, Point const &q){
  68. 		return !(p < q);
  69.  
  70. 		//cout << p.out() << " " << q.out() << " -> " << orientation(v[0], p, q) << '\n';
  71. 		//return orientation(v[0], p, q) == 1;
  72. 	});
  73.  
  74.  
  75. 	for (int i = 0; i < v.size(); ++i)
  76. 		cerr << v[i].x << "," << v[i].y << " -- ";
  77. 	cerr << '\n';
  78.  
  79. 	vector<Point> hull;
  80. 	for (Point p : v)
  81. 	{
  82. 		while (hull.size() >= 2)
  83. 		{
  84. 			Point a = hull[hull.size() - 2];
  85. 			Point b = hull.back();
  86.  
  87. 			if (orientation(a, b, p) != 1)
  88. 				hull.pop_back();
  89. 			else break;
  90. 		}
  91. 		hull.pb(p);
  92. 	}
  93.  
  94. 	cout << hull.size() << '\n';
  95. 	for (Point p : hull)
  96. 		cout << p.x << " " << p.y << '\n';
  97. 	*/
  98. 	return 0;
  99. }
  100.  
Success #stdin #stdout 0s 4768KB
comments (?)
stdin
copy 
6

3 3
4 3
2 1
2 5
4 4
6 3
stdout
copy 
2,1 -- 2,5 -- 3,3 -- 4,3 -- 4,4 -- 6,3 --
https://ideone.com/LH7fYM
language:
C++14 (gcc 8.3)
created:
3 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!