Pagini recente » Cod sursa (job #1753514) | Cod sursa (job #2834764) | Autentificare | Cod sursa (job #2274531) | Cod sursa (job #1922940)
#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;
double 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 j,i,pos,m;
double x,y;
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&m);
pos = 1;
n=1;
for(i=1;i<=m;i++)
{
scanf("%lf%lf",&x,&y);
for(j=i-1;j>=1;j--)
if(x==v[i].x && y==v[i].y)
break;
v[n].x = x;
v[n].y = y;
if(v[n].y < v[pos].y || (v[n].y==v[pos].y && v[n].x < v[pos].x))
pos = i;
n++;
}
n--;
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);
}