Pagini recente » Cod sursa (job #2704447) | Cod sursa (job #559748) | Cod sursa (job #323828) | Cod sursa (job #966966) | Cod sursa (job #1559518)
#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;
}