Pagini recente » Cod sursa (job #1823204) | Cod sursa (job #2725894) | Cod sursa (job #2295506) | Cod sursa (job #605332) | Cod sursa (job #1375528)
#include <cstdio>
#include <cmath>
#include <algorithm>
#define f first
#define s second
#define eps 1e-12
#define pairr pair < double , double >
using namespace std;
int b[125000],n,k,i,instr;
bool ok[125000];
pairr a[125000];
int cmpp(double x,double y)
{
if (x+eps<y)return -1;
else if (y+eps<x)return 1;
return 0;
}
int cmp(pairr a,pairr b,pairr c)
{
double A,B,C;
A=a.s-b.s;
B=b.f-a.f;
C=a.f*b.s-b.f*a.s;
return (cmpp(A*c.f+B*c.s+C,0));
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d\n",&n);
for (i=1; i<=n; i++)
{
scanf("%lf %lf\n",&a[i].f,&a[i].s);
}
sort(a+1,a+n+1);
ok[2]=true;
i=3;
instr=0;
b[++k]=1;
b[++k]=2;
while(ok[1]==false)
{
while (ok[i]==true)
{
if (i==n)instr=1;
if (instr==1)i--;
else i++;
}
while(k>=2&&cmp(a[b[k-1]],a[b[k]],a[i])==-1)
{
ok[b[k--]]=false;
}
b[++k]=i;
ok[i]=true;
}
printf("%d\n",k-1);
for (i=2; i<=k; i++)
printf("%lf %lf\n",a[b[i]].f,a[b[i]].s);
return 0;
}