Pagini recente » Cod sursa (job #2949344) | Cod sursa (job #319405) | Cod sursa (job #2791513) | Cod sursa (job #718959) | Cod sursa (job #1559404)
#include <cstdio>
#define maxn 120002
#define EPS 1e-12
using namespace std;
struct pereche{
double x,y;
} V[maxn];
int N,h = 2,S[maxn];
bool viz[maxn];
inline void swap(pereche &a,pereche &b){
pereche aux = a;
a = b;
b = aux;
}
inline double produs_in_cruce(const pereche &A,const pereche &B,const pereche &C){
return (A.x - C.x) * (B.y - C.y) - (B.x - C.x) * (A.y - C.y);
}
void quick_sort(pereche a[],int inf,int sup){
int i = inf,j = sup;
pereche x = a[(i+j)/2];
do{
while(i < sup && (a[i].x <= x.x))i++;
while(j > inf && (a[j].x >= x.x))j--;
if(i<=j){
swap(a[i],a[j]);
i++;j--;
}
}while( i <= j );
if(inf < j)quick_sort(a,inf,j);
if(i < sup)quick_sort(a,i,sup);
}
int main(){
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d ",&N);
int i,p = 1;
for(i = 1;i <= N;++i)
scanf("%lf %lf ",&V[i].x,&V[i].y);
//quick_sort(V,1,N);
sort(V+1,V+N+1);
S[1] = 1;
S[2] = 2;
viz[2] = true;
for(i = 1;i > 0; i += (p = (i == N ? -p : p)))if(viz[i] == false){
while(h >= 2 && produs_in_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]].x,V[S[i]].y);
printf("\n");
return 0;
}