Pagini recente » Cod sursa (job #2886644) | Cod sursa (job #2642847) | Cod sursa (job #1043748) | Cod sursa (job #447161) | Cod sursa (job #1434695)
#include <cstdio>
#include <algorithm>
#define eps 1e-12
using namespace std;
struct punct
{
double x;
double y;
};
punct a[120001];
bool cmp(punct a, punct b)
{
if (a.x<b.x) return true;
else if (a.x>b.x) return false;
else
{
if (a.y<b.y) return true;
else return false;
}
}
int comp(double a, double b)
{
if (a+eps<b) return 1;
if (b+eps<a) return -1;
return 0;
}
int determinant(punct a, punct b, punct c)
{
int det=a.x * b.y + c.x * a.y + b.x * c.y - c.x * b.y - b.x * a.y - a.x * c.y;
return comp(det,0);
}
int st[120001],n,i,nr,nr1,q;
bool ok[120001];
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].x,&a[i].y);
sort(a+1,a+n+1,cmp);
st[1]=1;
st[2]=2;
nr=2;
ok[2]=true;
q=1;
i=3;
while (!ok[1])
{
while (ok[i])
{
if (i==n) q=-1;
i+=q;
}
while (nr>=2 && determinant(a[st[nr-1]],a[st[nr]],a[i])==-1) ok[st[nr--]]=false;
st[++nr]=i;
ok[i]=true;
}
nr1=nr-1;
printf("%d\n",nr1);
for (i=2; i<=nr1+1; i++) printf("%lf %lf\n",a[st[i]].x,a[st[i]].y);
return 0;
}