Cod sursa(job #2245957)

Utilizator VladTiberiuMihailescu Vlad Tiberiu VladTiberiu Data 26 septembrie 2018 11:51:16
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include "bits/stdc++.h"

using namespace std;

const int NMax = 120003;

struct Point{
  long double x, y;
};

Point Points[NMax];
int n;

long double UnghiPolar(Point A, Point B, Point C){
  return (B.y - A.y) * (C.x - A.x) - (C.y - A.y) * (B.x - A.x);
}
bool cmp(Point x, Point y){
  return (UnghiPolar(Points[1],x,y) >= 0);
}
int main(){
  cin >> n;
  int lr = 1;
  for(int i = 1; i <= n; ++i){
    cin >> Points[i].x >> Points[i].y;
    if(Points[i].x == Points[lr].x){
      if(Points[i].y < Points[lr].y){
        lr = i;
      }
    }
    if(Points[i].x < Points[lr].x){
      lr = i;
    }
  }
  swap(Points[lr], Points[1]);
  sort(Points + 2, Points + 1 + n, cmp);
  /*for(int i = 1; i <= n; ++i){
    cout << Points[i].x << ' ' << Points[i].y << '\n';
  }*/
  int top = 0;
  int st[NMax];
  st[++top] = 1;
  st[++top] = 2;
  for(int i = 3; i <= n; ++i){
    while(top && UnghiPolar(Points[st[top - 1]], Points[st[top]], Points[i]) < 0){
      top--;
    }
    st[++top] = i;
  }
  cout << top << '\n';
  for(int i = top; i >= 1; --i){
    cout << fixed << setprecision(13) << Points[st[i]].x << ' ' << Points[st[i]].y << '\n';
  }
}