Pagini recente » Cod sursa (job #40256) | Cod sursa (job #2838910) | Cod sursa (job #1612146) | Cod sursa (job #2782168) | Cod sursa (job #2060510)
#include <stdio.h>
#include <algorithm>
using namespace std;
#define max_n 120001
int n,i,h;
typedef struct punct
{
double x,y;
};
punct p[max_n],v[max_n];
int s[max_n],ok[max_n];
bool cmp(const punct &a,const punct &b)
{
if(a.y==b.y)
return a.x<b.x;
return a.y<b.y;
}
int semn(punct a,punct b,punct c)
{
return a.x*b.y+b.x*c.y+a.y*c.x-b.y*c.x-c.y*a.x-a.y*b.x;
}
void rezolva()
{
int k,q;
sort(v+1,v+n+1,cmp);
s[1]=1; s[2]=2;
ok[2]=1;
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])<0)
{
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);
printf("%lf %lf\n",v[s[h+1]].x,v[s[h+1]].y);
for (i=2; i<=h; i++)
printf("%lf %lf\n",v[s[i]].x,v[s[i]].y);
return 0;
}