Cod sursa(job #2289329)

Utilizator ZappaManIosif Adrian-Mihai ZappaMan Data 24 noiembrie 2018 13:22:08
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <stdio.h>
#include <utility>
#include <algorithm>
#include <stack>

struct Point {
   double x, y;
};

using namespace std;

const int NMAX = 120005;
const double EPS = 1e-12;

int N;
Point points[NMAX];
bool vis[NMAX];
int st[NMAX];
int head = 0;


double cp(Point O, Point A, Point B) {
   return (A.x - O.x) * (B.y - O.y) - (B.x - O.x) * (A.y - O.y);
}

struct Point_cmp {
   inline bool operator() (const Point& p1, const Point& p2) {
      if (p1.x == p2.x) {
         return p1.y < p2.y;
      }
      return p1.x < p2.x;
   }
};



using namespace std;

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

   scanf("%d", &N);

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

   st[++head] = 1;
   st[++head] = 2;
   vis[2] = true;

   sort(points + 1, points + N + 1, Point_cmp());
   for (int i = 3, p = 1; i > 0; i += (p = (i == N) ? -p : p)) {
      if (vis[i]) {
         continue;
      }
      while (head >= 2 && (cp(points[st[head - 1]], points[st[head]], points[i]) < EPS)) {
         vis[st[head--]] = false;
      }
      st[++head] = i;
      vis[i] = true;
   }

   printf("%d\n", head-1);

   for (int i = 1; i < head; ++i) {
      printf("%.6lf %.6lf\n", points[st[i]].x, points[st[i]].y);
   }

   fclose(stdin);
   fclose(stdout);
   return 0;
}