Pagini recente » Cod sursa (job #982549) | Cod sursa (job #2530066) | Cod sursa (job #358416) | Cod sursa (job #128970) | Cod sursa (job #1824961)
#include <cstdio>
#include <cmath>
#include <algorithm>
#define eps 1.e-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)
LL=p[i];
else if(LL.y == p[i].y && LL.x > p[i].x)
LL=p[i];
sort(p, 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(int i=0; i<top; i++)
printf("%.6lf %.6lf\n",p[h[i]].x,p[h[i]].y);
return 0;
}