test/geometry/convex-hull/aoj-cgl-Convex-Hull.test.cpp

View this file on GitHub
Last update: 2023-05-29 14:59:47+08:00
Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_4_A

Depends on

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_4_A"

#include <iostream>
#include <algorithm>
#include "../../../library/geometry/point.hpp"
#include "../../../library/geometry/convex-hull.hpp"
using namespace std;
using namespace felix;
using namespace geometry;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	vector<Point<long long>> a(n);
	for(int i = 0; i < n; i++) {
		cin >> a[i];
	}
	auto ans = convex_hull(a);
	auto it = min_element(ans.begin(), ans.end(), [](Point<long long> a, Point<long long> b) {
		return a.y != b.y ? (a.y < b.y) : (a.x < b.x);
	});
	rotate(ans.begin(), it, ans.end());
	cout << ans.size() << "\n";
	for(int i = 0; i < (int) ans.size(); i++) {
		cout << ans[i].x << " " << ans[i].y << "\n";
	}
	return 0;
}

#line 1 "test/geometry/convex-hull/aoj-cgl-Convex-Hull.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=CGL_4_A"

#include <iostream>
#include <algorithm>
#line 3 "library/geometry/point.hpp"
#include <cmath>

namespace felix {

namespace geometry {

template<class T>
struct Point {
	T x, y;

	Point(T a = 0, T b = 0) : x(a), y(b) {}
	Point(const std::pair<T, T>& p) : x(p.first), y(p.second) {}

	explicit constexpr operator std::pair<T, T>() const { return std::pair<T, T>(x, y); }

	constexpr Point& operator+=(const Point& rhs) & {
		x += rhs.x, y += rhs.y;
		return *this;
	}

	constexpr Point& operator-=(const Point& rhs) & {
		x -= rhs.x, y -= rhs.y;
		return *this;
	}

	constexpr Point& operator*=(const T& rhs) & {
		x *= rhs, y *= rhs;
		return *this;
	}

	constexpr Point& operator/=(const T& rhs) & {
		x /= rhs, y /= rhs;
		return *this;
	}

	constexpr Point operator+() const { return *this; }
	constexpr Point operator-() const { return Point(-x, -y); }
	friend constexpr Point operator+(Point lhs, Point rhs) { return lhs += rhs; }
	friend constexpr Point operator-(Point lhs, Point rhs) { return lhs -= rhs; }
	friend constexpr Point operator*(Point lhs, T rhs) { return lhs *= rhs; }
	friend constexpr Point operator/(Point lhs, T rhs) { return lhs /= rhs; }
	constexpr bool operator==(const Point& rhs) const { return x == rhs.x && y == rhs.y; }
	constexpr bool operator!=(const Point& rhs) const { return !(*this == rhs); }

	// rotate counter-clockwise
	constexpr Point rotate(T theta) const {
		T sin_t = std::sin(theta), cos_t = std::cos(theta);
		return Point(x * cos_t - y * sin_t, x * sin_t + y * cos_t);
	}

	friend constexpr T abs2(Point p) { return p.x * p.x + p.y * p.y; }
	friend constexpr long double abs(Point p) { return std::sqrt(abs2(p)); }
	friend constexpr long double angle(Point p) { return std::atan2(p.y, p.x); }
	friend constexpr T dot(Point lhs, Point rhs) { return lhs.x * rhs.x + lhs.y * rhs.y; }
	friend constexpr T cross(Point lhs, Point rhs) { return lhs.x * rhs.y - lhs.y * rhs.x; }

	friend constexpr std::istream& operator>>(std::istream& in, Point& p) {
		return in >> p.x >> p.y;
	}
};

} // namespace geometry

} // namespace felix
#line 2 "library/geometry/convex-hull.hpp"
#include <vector>
#line 4 "library/geometry/convex-hull.hpp"
#include <functional>
#line 6 "library/geometry/convex-hull.hpp"

namespace felix {

namespace geometry {

// counter-clockwise order
template<class T>
std::vector<Point<T>> convex_hull(std::vector<Point<T>> p) {
	int n = (int) p.size();
	std::sort(p.begin(), p.end(), [](const Point<T>& a, const Point<T>& b) {
		return a.x == b.x ? (a.y < b.y) : (a.x < b.x);
	});
	auto build = [&]() {
		std::vector<Point<T>> upper = {p[0], p[1]};
		for(int i = 2; i < n; ++i) {
			while(upper.size() >= 2) {
				if(cross(upper.end()[-1] - upper.end()[-2], p[i] - upper.end()[-1]) > 0) {
					upper.pop_back();
				} else {
					break;
				}
			}
			upper.push_back(p[i]);
		}
		return upper;
	};
	std::vector<Point<T>> upper = build();
	std::reverse(p.begin(), p.end());
	std::vector<Point<T>> lower = build();
	lower.pop_back();
	upper.insert(upper.end(), lower.begin() + 1, lower.end());
	std::reverse(upper.begin(), upper.end());
	return upper;
}

} // namespace geometry

} // namespace felix
#line 7 "test/geometry/convex-hull/aoj-cgl-Convex-Hull.test.cpp"
using namespace std;
using namespace felix;
using namespace geometry;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	vector<Point<long long>> a(n);
	for(int i = 0; i < n; i++) {
		cin >> a[i];
	}
	auto ans = convex_hull(a);
	auto it = min_element(ans.begin(), ans.end(), [](Point<long long> a, Point<long long> b) {
		return a.y != b.y ? (a.y < b.y) : (a.x < b.x);
	});
	rotate(ans.begin(), it, ans.end());
	cout << ans.size() << "\n";
	for(int i = 0; i < (int) ans.size(); i++) {
		cout << ans[i].x << " " << ans[i].y << "\n";
	}
	return 0;
}