Pagini recente » Cod sursa (job #54730) | Cod sursa (job #1537108) | Cod sursa (job #1573149) | Cod sursa (job #2027912) | Cod sursa (job #695417)
Cod sursa(job #695417)
#include <stdio.h>
#include <algorithm>
#define NMAX 120005
#define pdd pair <double,double>
#define x first
#define y second
#define eps 0.000001
using namespace std;
int n,r,st[NMAX];
pdd A[NMAX];
bool in[NMAX];
void read()
{
scanf("%d",&n);
int i;
for (i=1; i<=n; i++)
scanf("%lf%lf",&A[i].x,&A[i].y);
}
inline int semn(pdd a,pdd b,pdd c)
{
double A=a.y-b.y;
double B=b.x-a.x;
double C=a.x*b.y-b.x*a.y;
double val=(A*c.x+B*c.y+C);
return (val<eps);
}
void solve()
{
int i,pas;
st[++r]=1; st[++r]=2; in[2]=1; i=3; pas=1;
while (!in[1])
{
while (in[i])
{
if (i==n)
pas=-1;
i+=pas;
}
while (r>=2 && semn(A[st[r-1]],A[st[r]],A[i]))
in[st[r]]=0,r--;
st[++r]=i; in[i]=1;
}
r--;
printf("%d\n",r);
for (i=1; i<=r; 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(A+1,A+n+1);
solve();
return 0;
}