Cod sursa(job #1582375)

Utilizator PTAdrian64Pop-Tifrea Adrian PTAdrian64 Data 27 ianuarie 2016 21:07:43
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <cstdio>
#define nmax 120005
#include <algorithm>

using namespace std;

typedef pair<double,double> Point;

int N;
Point v[nmax];

inline double produsx(const Point &a,const Point &b,const Point &c){
  return (b.first - a.first) * (c.second - a.second) - (b.second - a.second) * (c.first - a.first);
}

inline bool cmp(const Point &a,const Point &b){
  return produsx(v[1],a,b) < 0;
}

int main(){

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

  scanf("%d ",&N);
  int i,p;

  for(i = 1;i <= N;++i){
    scanf("%lf %lf ",&v[i].first,&v[i].second);
    if(i == 1 || v[p] > v[i])p = i;
  }

  swap(v[1],v[p]);
  sort(v+2,v+N+1,cmp);

  int h = 2;
  Point S[nmax];
  S[1] = v[1];
  S[2] = v[2];
  for(i = 3;i <= N;++i){

    while(h >= 2 && produsx(S[h-1],S[h],v[i]) > 0)h--;
    S[++h] = v[i];
    
  }

  printf("%d\n",h);
  for(i = h;i > 0;--i)printf("%lf %lf\n ",S[i].first,S[i].second);
  
  return 0;
}