Cod sursa(job #2402499)

Utilizator mateicosCostescu Matei mateicos Data 10 aprilie 2019 19:11:04
Problema Infasuratoare convexa Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <cstdio>
#include <algorithm>
#include <cmath>

using namespace std;

const double eps = 1e-12;

struct P{
  double x, y;
  double pt;
}v[120005];

int st[120005];

double cp(P a, P b, P c){
  return (b.x - a.x) * (c.y - b.y) - (b.y - a.y) * (c.x - b.x);
}

int ccw(P a, P b, P c){
  double ccp = cp(a, b, c);
  if(ccp >= -eps)
    return 1;
  return 0;
}

int cmp(P a, P b){
  return a.pt < b.pt;
}

int main()
{
    freopen("infasuratoare.in", "r", stdin);
    freopen("infasuratoare.out", "w", stdout);
    int n, i, mn, k;
    scanf("%d", &n);
    mn = 0;
    for(i = 0;i < n;i++){
      scanf("%lf%lf", &v[i].x, &v[i].y);
      v[i].pt = atan2(v[i].y, v[i].x);
      if(v[i].x < v[mn].x || (v[i].x == v[mn].x && v[i].y < v[mn].y))
        mn = i;
    }
    for(i = 0;i < n;i++){
      v[i].pt = atan2(v[i].y - v[mn].y, v[i].x - v[mn].x);
    }
    v[mn].pt = -1;
    sort(v, v + n, cmp);
    k = 1;
    for(i = 1;i < n;i++){
      while(k > 1 && !ccw(v[st[k - 2]], v[st[k - 1]], v[i]))
        k--;
      st[k++] = i;
    }
    while(k > 1 && !ccw(v[st[k - 2]], v[st[k - 1]], v[0]))
      k--;
    printf("%d\n", k);
    for(i = 0;i < k;i++){
      printf("%f %f\n", v[st[i]].x, v[st[i]].y);
    }
    return 0;
}