Cod sursa(job #2204540)

Utilizator Robert_VRVRobert Vadastreanu Robert_VRV Data 16 mai 2018 12:27:13
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <vector>

struct Point {
  double x;
  double y;
  bool operator <(const Point& other) const {
    return this->x < other.x || (this->x == other.x && this->y < other.y);
  }
};

double det(const Point& a, const Point& b, const Point& c) {
  return (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y);
}

Point point;
bool cmp(const Point& a, const Point& b) {
  return det(point, a, b) > 0;
}

int main() {
  freopen("infasuratoare.in", "r", stdin);
  freopen("infasuratoare.out", "w", stdout);
  int n;
  scanf("%d", &n);
  Point points[1 + n];
  int pozMin = 1;

  for (int i = 1; i <= n; i++) {
    scanf("%lf%lf", &points[i].x, &points[i].y);
    if (points[i] < points[pozMin])
      pozMin = i;
  }

  point = points[pozMin];
  std::swap(points[1], points[pozMin]);
  std::sort(points + 2, points + n + 1, cmp);
  std::vector<Point> answer;
  answer.push_back(points[1]);
  answer.push_back(points[2]);

  for (int i = 3; i <= n; i++) {
    while (answer.size() >= 2 && det(*(answer.rbegin() + 1), *answer.rbegin(), points[i]) <= 0)
      answer.pop_back();
    answer.push_back(points[i]);
  }

  printf("%d\n", (int)answer.size());
  std::vector<Point> :: iterator it;
  for (it = answer.begin(); it != answer.end(); it++)
    printf("%lf %lf\n", (*it).x, (*it).y);


  fclose(stdin);
  fclose(stdout);

  return 0;
}