Pagini recente » Cod sursa (job #1034948) | Profil andradacojocaru | Cod sursa (job #976691) | Cod sursa (job #2488074) | Cod sursa (job #1826503)
#include <cstdio>
#include <cmath>
#include <algorithm>
#define eps 1e-12
using namespace std;
int const NMAX=120000;
struct point
{
double x,y;
}LL,p[NMAX+5];
int h[NMAX+5];
int ccw(point p1, point p2, point p3)
{
double cp;
cp=(p2.x-p1.x)*(p3.y-p2.y)-(p2.y-p1.y)*(p3.x-p2.x);
if(fabs(cp)< eps) return 0;
if(cp >= eps) return 1;
return -1;
}
bool cmp(point a, point b)
{
int c=ccw(LL,a,b);
if(c == 1) return 1;
if(c == -1) return 0;
}
int main()
{
freopen("infasuratoare.in", "r",stdin);
freopen("infasuratoare.out", "w",stdout);
int n;
scanf("%d", &n);
for(int i=0; i<n; i++)
scanf("%lf%lf",&p[i].x, &p[i].y);
LL=p[0];
for(int i=1; i<n; i++)
if(LL.y - p[i].y >= eps)
swap(LL,p[i]);
else if((fabs(p[i].y-LL.y) < eps) && (LL.x - p[i].x >= eps))
swap(LL,p[i]);
sort(p+1, p+n, cmp);
p[0]=LL;
p[n]=LL;
h[0]=0;
h[1]=1;
int top=1,i=2;
while(i<=n)
{
if(ccw(p[h[top-1]], p[h[top]], p[i]) > 0){
top++;
h[top]=i;
i++;
}
else top--;
}
printf("%d\n", top);
for(i=0; i<top; i++)
printf("%.6lf %.6lf\n",p[h[i]].x,p[h[i]].y);
return 0;
}