fork download
copy 
  1. #include <cmath>
  2. #include <vector>
  3. #include <iostream>
  4. #include <algorithm>
  5. using namespace std;
  6. // ------ Classes ------ //
  7. class Point {
  8. public:
  9. 	long double px, py;
  10. 	Point() : px(0), py(0) {};
  11. 	Point(long double px_, long double py_) : px(px_), py(py_) {};
  12. 	friend bool operator==(const Point& p1, const Point& p2) { return p1.px == p2.px && p1.py == p2.py; }
  13. 	friend bool operator!=(const Point& p1, const Point& p2) { return p1.px != p2.px || p1.py != p2.py; }
  14. 	friend bool operator<(const Point& p1, const Point& p2) { return p1.px < p2.px ? true : (p1.px == p2.px && p1.py < p2.py); }
  15. 	friend bool operator>(const Point& p1, const Point& p2) { return p1.px > p2.px ? true : (p1.px == p2.px && p1.py > p2.py); }
  16. 	friend bool operator<=(const Point& p1, const Point& p2) { return !(p1 > p2); }
  17. 	friend bool operator>=(const Point& p1, const Point& p2) { return !(p1 < p2); }
  18. 	friend Point operator+(const Point& p1, const Point& p2) { return Point(p1.px + p2.px, p1.py + p2.py); }
  19. 	friend Point operator-(const Point& p1, const Point& p2) { return Point(p1.px - p2.px, p1.py - p2.py); }
  20. 	friend Point operator*(const Point& p1, long double d) { return Point(p1.px * d, p1.py + d); }
  21. 	friend Point operator*(long double d, const Point& p1) { return p1 * d; }
  22. 	friend Point operator/(const Point& p1, long double d) { return Point(p1.px / d, p1.py / d); }
  23. 	Point& operator+=(const Point& p1) { px += p1.px; py += p1.py; return *this; }
  24. 	Point& operator-=(const Point& p1) { px -= p1.px; py -= p1.py; return *this; }
  25. 	Point& operator*=(long double d) { px *= d; py *= d; return *this; }
  26. 	Point& operator/=(long double d) { px /= d; py /= d; return *this; }
  27. };
  28. class Segment {
  29. public:
  30. 	Point p1, p2;
  31. 	Segment() : p1(Point()), p2(Point()) {};
  32. 	Segment(Point p1_, Point p2_) : p1(p1_), p2(p2_) {};
  33. 	Segment(long double p1x, long double p1y, long double p2x, long double p2y) : p1(Point(p1x, p1y)), p2(Point(p2x, p2y)) {};
  34. 	friend bool operator==(const Segment& s1, const Segment& s2) { return (s1.p1 == s2.p1 && s1.p2 == s2.p2) || (s1.p1 == s2.p2 && s1.p2 == s2.p1); }
  35. 	friend bool operator!=(const Segment& s1, const Segment& s2) { return !(s1 == s2); }
  36. };
  37. class Line {
  38. public:
  39. 	Point p1, p2;
  40. 	Line() : p1(Point()), p2(Point()) {};
  41. 	Line(Point p1_, Point p2_) : p1(p1_), p2(p2_) {};
  42. 	Line(long double p1x, long double p1y, long double p2x, long double p2y) : p1(Point(p1x, p1y)), p2(Point(p2x, p2y)) {};
  43. 	friend bool operator==(const Line& s1, const Line& s2) { return (s1.p1 == s2.p1 && s1.p2 == s2.p2) || (s1.p1 == s2.p2 && s1.p2 == s2.p1); }
  44. 	friend bool operator!=(const Line& s1, const Line& s2) { return !(s1 == s2); }
  45. };
  46. // ------ Functions ------ //
  47. long double norm(const Point& a) { return a.px * a.px + a.py * a.py; }
  48. long double abs(const Point& a) { return sqrtl(norm(a)); }
  49. long double dot(const Point& a, const Point& b) { return a.px * b.px + a.py * b.py; }
  50. long double crs(const Point& a, const Point& b) { return a.px * b.py - a.py * b.px; }
  51. int ccw(Point p0, Point p1, Point p2) {
  52. 	Point a = p1 - p0, b = p2 - p0;
  53. 	if (crs(a, b) > 1e-10) return 1;
  54. 	if (crs(a, b) < -1e-10) return -1;
  55. 	if (dot(a, b) < -1e-10) return 2;
  56. 	if (norm(a) < norm(b)) return -2;
  57. 	return 0;
  58. }
  59. vector<Point> convex_hull(vector<Point> v) {
  60. 	if (v.size() < 3) return v;
  61. 	sort(v.begin(), v.end());
  62. 	vector<Point> u = { v[0], v[1] }, l = { v[v.size() - 1], v[v.size() - 2] };
  63. 	for (int i = 2; i < v.size(); i++) {
  64. 		for (int n = u.size(); n >= 2 && ccw(u[n - 2], u[n - 1], v[i]) >= 0; n--) u.pop_back();
  65. 		u.push_back(v[i]);
  66. 	}
  67. 	for (int i = v.size() - 3; i >= 0; i--) {
  68. 		for (int n = l.size(); n >= 2 && ccw(l[n - 2], l[n - 1], v[i]) >= 0; n--) l.pop_back();
  69. 		l.push_back(v[i]);
  70. 	}
  71. 	reverse(l.begin(), l.end());
  72. 	for (int i = u.size() - 2; i >= 1; i--) l.push_back(u[i]);
  73. 	return l;
  74. }
  75. // ------ Main ------ //
  76. int n; vector<Point> v;
  77. int rec(vector<Point> v1) {
  78. 	vector<Point> v2 = convex_hull(v1);
  79. 	sort(v2.begin(), v2.end());
  80. 	if (v1.size() == v2.size()) return v1.size() < 3 ? v1.size() - 1 : (v1.size() == 3 ? v1.size() : v1.size() * 2 - 3);
  81. 	vector<Point> v3;
  82. 	for (int i = 0; i < v1.size(); i++) {
  83. 		if (!binary_search(v2.begin(), v2.end(), v1[i])) v3.push_back(v1[i]);
  84. 	}
  85. 	vector<Point> v4 = convex_hull(v3);
  86. 	if (v4.size() == 1) return v2.size() * 2;
  87. 	if (v4.size() == 2) return v2.size() * 2 + 3;
  88. 	return rec(v3) + v2.size() * 2 + v4.size();
  89. }
  90. int main() {
  91. 	cin >> n; v.resize(n);
  92. 	for (int i = 0; i < v.size(); i++) cin >> v[i].px >> v[i].py;
  93. 	cout << rec(v) << endl;
  94. 	return 0;
  95. }
Success #stdin #stdout 0s 3424KB
comments (?)
stdin
copy 
4
0 0
1 2
2 0
1 1
stdout
copy 
6
https://ideone.com/SMbXgg
language:
C++14 (gcc 8.3)
created:
7 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!