Pagini recente » Cod sursa (job #1894379) | Cod sursa (job #579301) | Cod sursa (job #174052) | Cod sursa (job #3156379) | Cod sursa (job #534962)
Cod sursa(job #534962)
#include <stdio.h>
#include <algorithm>
using namespace std;
#define eps 1e-12
int n,i,h;
typedef struct punct {
double x,y;
};
punct p[120001],v[120001];
int s[120001],ok[120005];
inline int cmp1(double a,double b) {
if (a+eps<b) return -1;
if (b+eps<a) return 1;
return 0;
}
bool cmp(const punct &a,const punct &b) {
int t;
t=cmp1(a.x,b.x);
if (t!=0) return t==-1;
return (cmp1(a.y,b.y)==-1);
}
int semn(punct a,punct b,punct c) {
double A,B,C;
A = a.y-b.y;
B = b.x-a.x;
C = a.x*b.y - b.x*a.y;
return cmp1(A*c.x+B*c.y+C,0);
}
void rezolva() {
int k,q;
sort(v+1,v+n+1,cmp);
ok[2]=1;
s[1]=1; s[2]=2;
k=2;
i=3;
q=1;
while (!ok[1]) {
while (ok[i]) {
if (i==n) q=-1;
i+=q;
}
while (k>=2 && semn(v[s[k-1]],v[s[k]],v[i])==-1) {
ok[s[k--]]=0;
}
s[++k]=i;
ok[i]=1;
}
h=k-1;
}
int main () {
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
for (i=1; i<=n; i++)
scanf("%lf%lf",&v[i].x,&v[i].y);
rezolva();
printf("%d\n",h);
for (i=2; i<=h+1; i++)
printf("%lf %lf\n",v[s[i]].x,v[s[i]].y);
return 0;
}