Pagini recente » Cod sursa (job #2394307) | Cod sursa (job #241660) | Cod sursa (job #1683490) | Cod sursa (job #127678) | Cod sursa (job #720594)
Cod sursa(job #720594)
#include<cstdio>
#include<algorithm>
#define INF 1e9+5
#define NMax 120005
using namespace std;
double x[NMax],y[NMax];
int v[NMax],n,p0,st[NMax];
bool cmp (int i,int j)
{
return (double)(x[i]-x[p0])*(y[j]-y[p0])<(double)(x[j]-x[p0])*(y[i]-y[p0]);
}
long double semn (int x1,int x2,int x3)
{
return (long double)(x[x2]-x[x1])*(y[x3]-y[x1])-(x[x3]-x[x1])*(y[x2]-y[x1]);
}
void citire ()
{
//freopen("infasuratoare.in","r",stdin);
scanf("%d",&n);
for (int i=1; i<=n; i++)
{
scanf("%lf%lf",&x[i],&y[i]);
if (y[i]<y[p0] || (y[i]==y[p0] && x[i]<x[p0]))
p0=i;
}
}
void sortare ()
{
int i;
for (i=1; i<=n; i++)
if (i!=p0)
v[++v[0]]=i;
sort(v+1,v+v[0]+1,cmp);
}
void scanare_graham ()
{
st[0]=3; st[1]=p0;
st[2]=v[1]; st[3]=v[2];
for (int i=3; i<=v[0]; i++)
{
while (semn(st[st[0]-1],st[st[0]],v[i])>0) st[0]--;
st[++st[0]]=v[i];
}
}
void afisare ()
{
//freopen("infasuratoare.out","w",stdout);
printf("%d\n",st[0]);
printf("%lf %lf\n",x[p0],y[p0]);
reverse(st+1,st+st[0]+1);
for (int i=1; i<st[0]; i++)
printf("%lf %lf\n",x[st[i]],y[st[i]]);
}
int main ()
{
x[0]=INF; y[0]=INF;
citire();
sortare();
scanare_graham();
afisare();
return 0;
}