Pagini recente » Cod sursa (job #3137137) | Cod sursa (job #1750999) | Cod sursa (job #2566170) | Cod sursa (job #2371878) | Cod sursa (job #1922892)
#include <vector>
#include <cstdio>
#include <algorithm>
#include <cmath>
#define NMAX 120010
#define x first
#define y second
using namespace std;
typedef pair<double, double> punct;
punct v[NMAX],st[NMAX];
int n,head;
int cross_product(punct A,punct B,punct C)
{
return (C.y - A.y)*(B.x - A.x) - (B.y - A.y)*(C.x - A.x);
}
int cmp(punct p1,punct p2)
{
return cross_product(v[1],p1,p2) < 0;
}
void convex_hull()
{
int i;
st[1] = v[1];
st[2] = v[2];
head = 2;
for(i=3;i<=n;i++)
{
while(head>=2 && cross_product(st[head-1],st[head],v[i]) > 0)
head--;
st[++head] = v[i];
}
}
int main()
{
int i,pos;
double x,y;
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
pos = 1;
for(i=1;i<=n;i++)
{
scanf("%lf%lf",&x,&y);
v[i].x = x;
v[i].y = y;
if(v[i].y < v[pos].y || (v[i].y==v[pos].y && v[i].x < v[i].y))
pos = i;
}
swap(v[1],v[pos]);
sort(v+2,v + n + 1,cmp);
convex_hull();
printf("%d\n",head);
swap(st[head+1],st[1]);
for(i=head+1;i>=2;i--)
printf("%.6lf %.6lf\n",st[i].x,st[i].y);
}