Cod sursa(job #1559250)

Utilizator PTAdrian64Pop-Tifrea Adrian PTAdrian64 Data 30 decembrie 2015 14:55:28
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <cstdio>
#define nmax 120004
#include <algorithm>

using namespace std;



struct pereche{
  double x,y;
} V[nmax],S[nmax];

inline void swap(pereche &a,pereche &b){
  pereche aux = a;
  a = b;
  b = aux;
}

inline double cross_product(const pereche &A,const pereche &B,const pereche &C){
  return (B.x - A.x)*(C.y - A.y) - (B.y - A.y)*(C.x - A.x);
}

inline bool cmp(const pereche &A,const pereche &B){
  return cross_product(V[1],A,B)<0;
}

int N;

int main(){
  freopen("infasuratoare.in","r",stdin);
  freopen("infasuratoare.out","w",stdout);
  scanf("%d ",&N);
  int i,start,h = 2;
  for(i = 1;i <= N;++i){
    scanf("%lf %lf ",&V[i].x,&V[i].y);
    if(i == 1 || V[i].x < V[start].x || (V[i].x == V[start].x && V[i].y < V[start].y))start = i;
  }
  swap(V[1],V[start]);
  sort(V+2,V+N+1,cmp);

  S[1] = V[1];S[2] = V[2];
  for(i = 3;i <= N;++i){
    while(h >= 2 && cross_product(S[h-1],S[h],V[i])>0)h--;
    S[++h] = V[i];
  }
  
  printf("%d\n",h);
  for(i = h;i>=1;--i)printf("%lf %lf\n",S[i].x,S[i].y);
  printf("\n");

  return 0;
}