Cod sursa(job #1560059)

Utilizator PTAdrian64Pop-Tifrea Adrian PTAdrian64 Data 1 ianuarie 2016 16:22:12
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <cstdio>
#include <algorithm>
#define nmax 120003
#define x first
#define y second

using namespace std;

typedef pair<double,double> Point;

int N;
Point V[nmax],S[nmax];

void schimba(Point &a,Point &B){
  Point aux = a;
  a = B;
  B = aux;
}

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

inline bool panta(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].x,&V[i].y);
    if(i == 1 || V[i] < V[p])p = i;
  }
  schimba(V[1],V[p]);
    sort(V+2,V+N+1,panta);

  S[1] = V[1];
  S[2] = V[2];
  int H = 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 >= 1;--i)printf("%lf %lf\n",S[i].x,S[i].y);
  printf("\n");
    
  return 0;
}