Pagini recente » Cod sursa (job #2029283) | Cod sursa (job #2396018) | Istoria paginii runda/zvzx | Cod sursa (job #2254028) | Cod sursa (job #1557936)
#include <cstdio>
#include <algorithm>
#define Nmax 120045
#define x first
#define y second
using namespace std;
typedef pair <double, double> Point;
Point v[Nmax];
Point st[Nmax];
int n,head;
double cross(Point A,Point B,Point C)
{
return (C.y - A.y) * (B.x - A.x) - (C.x - A.x) * (B.y - A.y);
}
bool cmp(Point A,Point B)
{
return cross(v[1], A, B) < 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(st[head - 1], st[head] , v[i]) > 0)
head--;
st[++head] = v[i];
}
}
int main()
{
int pos = 1,i;
Point p;
double x,y;
freopen("infasuratoare.in","r",stdin);
//freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
for(i = 1;i<=n;i++)
{
scanf("%lf%lf",&v[i].x,&v[i].y);
if(v[i].y < v[pos].y || (v[i].y == v[pos].y && v[i].x < v[pos].y))
pos = i;
}
swap(v[1],v[pos]);
sort(v + 2, v + n + 1, cmp);
convex_hull();
printf("%d\n",head);
printf("%.9lf %.9lf\n",st[1].x,st[1].y);
for(i = head ;i >= 2;i--)
printf("%.9lf %.9lf\n",st[i].x,st[i].y);
}