Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <algorithm>
- #include <iostream>
- #include <vector>
- using namespace std;
- template <typename T>
- class _vertex
- {
- public:
- bool operator <(const _vertex& v) const
- {
- return (y != v.y) ? (y < v.y) : (x < v.x);
- }
- static T cross(const _vertex& o, const _vertex& a, const _vertex& b)
- {
- return (a.x - o.x)*(b.y - o.y) - (a.y - o.y)*(b.x - o.x);
- }
- private:
- friend istream& operator >>(istream& is, _vertex& v)
- {
- is >> v.x >> v.y;
- return is;
- }
- friend ostream& operator <<(ostream& os, const _vertex& v)
- {
- os << v.x << " " << v.y;
- return os;
- }
- private:
- T x, y;
- };
- using vertex = _vertex<int>;
- vector<vertex> find_convex_hull(vector<vertex>&& contour)
- {
- sort(contour.begin(), contour.end());
- if (contour.size() <= 3) return contour; // It should still be sorted to fulfill the required order.
- auto back = [](const vector<vertex>& container, size_t offset)
- {
- return *(container.rbegin() + offset);
- };
- vector<vertex> convex;
- for (auto it = contour.cbegin(); it != contour.cend(); it++)
- {
- while (convex.size() > 1 && vertex::cross(back(convex, 1), back(convex, 0), *it) <= 0) convex.pop_back();
- convex.push_back(*it);
- }
- size_t s = convex.size();
- for (auto it = contour.rbegin(); it != contour.rend(); it++)
- {
- while (convex.size() > s && vertex::cross(back(convex, 1), back(convex, 0), *it) <= 0) convex.pop_back();
- convex.push_back(*it);
- }
- return convex;
- }
- void test_case()
- {
- size_t n;
- cin >> n;
- vector<vertex> contour(n);
- for (auto& v : contour) cin >> v;
- auto convex = find_convex_hull(move(contour));
- cout << convex.size() << endl;
- for (const auto& v : convex) cout << v << endl;
- }
- int main()
- {
- size_t n;
- cin >> n;
- cout << n << endl;
- while (n--)
- {
- test_case();
- if (n > 0)
- {
- int s;
- cin >> s;
- cout << -1 << endl;
- }
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment