Cod sursa(job #1559518)

Utilizator PTAdrian64Pop-Tifrea Adrian PTAdrian64 Data 30 decembrie 2015 23:10:06
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <cstdio>
#include <algorithm>
#define nmax 120004
#define EPS 1e-12

using namespace std;

int N,S[nmax],H = 2;
pair <double,double> V[nmax];
bool viz[nmax];

inline double produs_cruce(pair <double,double> A,pair <double,double> B,pair <double,double> C){
   return (A.first - C.first)*(B.second - C.second) - (B.first - C.first)*(A.second - C.second);
}

int main(){

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

   scanf("%d ",&N);
   int i,j;
   for(i = 1;i <= N;++i)
      scanf("%lf %lf ",&V[i].first,&V[i].second);
   
   sort(V+1,V+N+1);
   S[1] = 1;
   S[2] = 2;
   viz[2] = true;
   
   for(i = 1,j = 1;i >0;i+=(j = (i == N ? -j : j)))if(viz[i] == false){
      while(H >= 2 && produs_cruce(V[S[H-1]],V[S[H]],V[i]) < EPS)viz[S[H--]] = false;
      S[++H] = i;
      viz[i] = true;
   }

   printf("%d\n",H-1);
   for(i = 1;i < H;++i)printf("%lf %lf\n",V[S[i]].first,V[S[i]].second);
   printf("\n");

   return 0;

}