Cod sursa(job #598606)

Utilizator Smaug-Andrei C. Smaug- Data 26 iunie 2011 15:18:04
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <cstdio>
#include <algorithm>
using namespace std;

#define MAXN 120010
#define INF (1<<30)

double X[MAXN], Y[MAXN];
int OP, IND[MAXN], S[MAXN];

struct cmp {
  bool operator()(const int &a, const int &b)const{
    return (double)(X[a]-X[OP])*(Y[b]-Y[OP]) < (double)(X[b]-X[OP])*(Y[a]-Y[OP]);
  }
};

inline double sign(int p1, int p2, int p3){
  return (long double) X[p1]*Y[p2]+X[p2]*Y[p3]+X[p3]*Y[p1]-Y[p1]*X[p2]-Y[p2]*X[p3]-Y[p3]*X[p1];
}

int main(){

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

  int N, i, cnt, t;
  
  scanf("%d", &N);
  X[0]=Y[0]=INF; OP=0;
  for(i=1; i<=N; i++){
    scanf("%lf %lf", X+i, Y+i);
    if(X[i] < X[OP] || (X[i]==X[OP] && Y[i]<Y[OP]))
      OP=i;
  }

  cnt=0;
  for(i=1; i<=N; i++)
    if(i!=OP)
      IND[++cnt]=i;

  sort(IND+1, IND+cnt+1, cmp());
  
  S[1]=OP; t=1;
  for(i=1; i<=cnt; i++){
    while(t>=2 && sign(S[t-1],S[t],IND[i]) > 0)
      t--;
    S[++t]=IND[i];
  }
  S[++t]=OP;

  printf("%d\n", t-1);
  for(i=t-1; i>0; i--){
    printf("%lf %lf\n", X[S[i]], Y[S[i]]);
  }

  return 0;

}