Pagini recente » Cod sursa (job #1705376) | Cod sursa (job #1323447) | Cod sursa (job #2148474) | Cod sursa (job #2061084) | Cod sursa (job #408806)
Cod sursa(job #408806)
#include <stdio.h>
#include <algorithm>
#define NMAX 120005
using namespace std;
struct pct
{
double x,y;
};
int n,PI,B[NMAX],r;
pct A[NMAX];
int st[NMAX],t;//stiva
void read()
{
scanf("%d",&n);
PI=1;
int i;
for (i=1; i<=n; i++)
{
scanf("%lf%lf",&A[i].x,&A[i].y);
if (A[i].x<A[PI].x || (A[i].x==A[PI].x && A[i].y<A[PI].y))
PI=i;
}
for (i=1; i<=n; i++)
if (i!=PI)
B[++r]=i;
}
bool comp(int i,int j)
{
return (double)(A[i].x - A[PI].x) * (A[j].y - A[PI].y) < (double)(A[j].x - A[PI].x) * (A[i].y - A[PI].y);
}
long double semn(int i1,int i2,int i3)
{
return (long double)A[i1].x * A[i2].y + A[i2].x * A[i3].y + A[i3].x * A[i1].y - A[i1].y * A[i2].x - A[i2].y * A[i3].x - A[i3].y * A[i1].x;
}
void infasuratoare()
{
int i;
for (i=1; i<=r; i++)
{
while (t>=2 && semn(st[t-1],st[t],B[i])>0)
t--;
st[++t]=B[i];
}
st[++t]=PI;
}
void show()
{
reverse(st+1,st+t+1);
int i;
printf("%d\n",t-1);
for (i=1; i<t; i++)
printf("%lf %lf\n",A[st[i]].x,A[st[i]].y);
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
read();
sort(B+1,B+r+1,comp);
st[++t]=PI;
infasuratoare();
show();
return 0;
}