Cod sursa(job #2587557)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 22 martie 2020 23:00:52
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.19 kb
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

class Point{
 public:
  Point(double x, double y):x_(x), y_(y) {}
  bool operator < (const Point& other) const {
    if (x() == other.x())
      return y() < other.y();
    return x() < other.x();
  }
  double x() const {return x_;}
  double y() const {return y_;}
 private:
  double x_, y_;
};
/**
  | a.x a.y 1|  | a.x        a.y         1|
  | b.x b.y 1| =| b.x - a.x  b.y - a.y   0| = (b.x - a.x)*(c.y-a.y) - (c.x - a.x)*(b.y - a.y)
  | c.x c.y 1|  | c.x - a.x  c.y - a.y   0| 
 */
double det(Point a, Point b, Point c)
{
  return (b.x() - a.x())*(c.y()-a.y()) - (c.x() - a.x())*(b.y() - a.y());
}

vector<Point> points;

void convexHull()
{
  sort(points.begin(), points.end());
  Point pmin = points.front();
  Point pmax = points.back();
  vector<Point> upper_envelope, lower_envelope;
  for (vector<Point>::iterator it = points.begin(); it != points.end(); ++it) {
    Point p = *it;
    if (det(pmin, pmax, p) >= 0) {
      while (upper_envelope.size() >= 2 &&
	     det(upper_envelope[(int)upper_envelope.size() - 2],
	 	 upper_envelope[(int)upper_envelope.size() - 1],
		 p) > 0)
	upper_envelope.pop_back();
      upper_envelope.emplace_back(p);
    }
  }
  for (vector<Point>::reverse_iterator it = points.rbegin(); it != points.rend(); ++it) {
    Point p = *it;
    if (det(pmax, pmin, p) >= 0) {
      while (lower_envelope.size() >= 2 &&
	     det(lower_envelope[(int)lower_envelope.size() - 2],
		 lower_envelope[(int)lower_envelope.size() - 1],
		 p) > 0)
	lower_envelope.pop_back();
      lower_envelope.emplace_back(p);
    }
  }

  printf("%d\n", (int)lower_envelope.size() + (int)upper_envelope.size() - 2);
  for (int i = 0; i < upper_envelope.size(); ++i)
    printf("%lf %lf\n", upper_envelope[i].x(), upper_envelope[i].y());
  for (int i = (int)lower_envelope.size() - 2; i > 0; --i)
    printf("%lf %lf\n", lower_envelope[i].x(), lower_envelope[i].y());
}

int main()
{
  freopen("infasuratoare.in", "r", stdin);
  freopen("infasuratoare.out", "w", stdout);

  int N;
  scanf("%d", &N);
  
  for (int i = 0; i < N; ++i) {
    double x, y;
    scanf("%lf%lf", &x, &y);
    points.emplace_back(x,y);
  }
  convexHull();
  
  return 0;
}