Pagini recente » Cod sursa (job #629534) | Cod sursa (job #2821406) | Cod sursa (job #1890750) | Cod sursa (job #335765) | Cod sursa (job #1559250)
#include <cstdio>
#define nmax 120004
#include <algorithm>
using namespace std;
struct pereche{
double x,y;
} V[nmax],S[nmax];
inline void swap(pereche &a,pereche &b){
pereche aux = a;
a = b;
b = aux;
}
inline double cross_product(const pereche &A,const pereche &B,const pereche &C){
return (B.x - A.x)*(C.y - A.y) - (B.y - A.y)*(C.x - A.x);
}
inline bool cmp(const pereche &A,const pereche &B){
return cross_product(V[1],A,B)<0;
}
int N;
int main(){
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d ",&N);
int i,start,h = 2;
for(i = 1;i <= N;++i){
scanf("%lf %lf ",&V[i].x,&V[i].y);
if(i == 1 || V[i].x < V[start].x || (V[i].x == V[start].x && V[i].y < V[start].y))start = i;
}
swap(V[1],V[start]);
sort(V+2,V+N+1,cmp);
S[1] = V[1];S[2] = V[2];
for(i = 3;i <= N;++i){
while(h >= 2 && cross_product(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;
}