Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <cmath>
- #include <algorithm>
- class TPoint {
- private:
- int X, Y;
- friend class TSetOfPoints;
- friend bool operator==(const TPoint&, const TPoint&);
- friend int CrossProduct(const TPoint&, const TPoint&);
- public:
- TPoint(int x = 0, int y = 0) : X(x), Y(y) {}
- int Length() const {
- return X * X + Y * Y;
- }
- const TPoint operator-() const {
- return TPoint(-X, -Y);
- }
- const TPoint& operator+=(TPoint p) {
- X += p.X;
- Y += p.Y;
- return *this;
- }
- const TPoint& operator-=(TPoint p) {
- *this += -p;
- return *this;
- }
- void Print(std::ostream& stream) {
- stream << X << " " << Y << "\n";
- }
- };
- const TPoint operator-(const TPoint& p1, const TPoint& p2) {
- TPoint p = p1;
- p -= p2;
- return p;
- }
- bool operator==(const TPoint& p1, const TPoint& p2) {
- return p1.X == p2.X && p1.Y == p2.Y;
- }
- int CrossProduct(const TPoint& p1, const TPoint& p2) {
- return p1.X * p2.Y - p1.Y * p2.X;
- }
- bool operator<(TPoint p1, TPoint p2) {
- return CrossProduct(p1, p2) > 0 || (CrossProduct(p1, p2) == 0 && p1.Length() < p2.Length());
- }
- class TSetOfPoints {
- private:
- unsigned Amount;
- std::vector<TPoint> Set;
- public:
- TSetOfPoints(unsigned a) : Amount(a), Set(Amount) {}
- void ReadFromStream(std::istream& stream) {
- for (auto iter = Set.begin(); iter != Set.end(); ++iter) {
- stream >> iter->X >> iter->Y;
- }
- }
- unsigned GetSize() const {
- return Amount;
- }
- std::vector<TPoint> ConvexHull() const {
- std::vector<TPoint> points = Set;
- TPoint z = points[0];
- for (TPoint p : points) {
- TPoint t = z - p;
- if (t.Y > 0 || (t.Y == 0 && t.X > 0)) {
- z = p;
- }
- }
- for (TPoint &p : points) {
- p -= z;
- }
- std::sort(points.begin(), points.end());
- auto last = std::unique(points.begin(), points.end());
- points.erase(last, points.end());
- std::vector<TPoint> hull;
- for (TPoint p : points) {
- while (hull.size() >= 2 && CrossProduct(hull[hull.size() - 2] - hull.back(), p - hull.back()) >= 0) {
- hull.pop_back();
- }
- hull.push_back(p);
- }
- for (TPoint &p : hull) {
- p += z;
- }
- return hull;
- }
- };
- TSetOfPoints Create(std::istream& stream) {
- unsigned n;
- std::cin >> n;
- TSetOfPoints t(n);
- t.ReadFromStream(stream);
- return t;
- }
- int main() {
- TSetOfPoints s = Create(std::cin);
- std::vector<TPoint> h = s.ConvexHull();
- std::cout << h.size() << std::endl;
- if (s.GetSize() & 1) {
- std::reverse(h.begin(), h.end());
- }
- for (TPoint p : h) {
- p.Print(std::cout);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement