Pagini recente » Cod sursa (job #70808) | Cod sursa (job #2117784) | Cod sursa (job #3166371) | Cod sursa (job #1360565) | Cod sursa (job #1697817)
#include <bits/stdc++.h>
using namespace std;
const int PMAX = 120005;
const double inf = 1.e12;
const double eps = 1.e-12;
struct POINT {
double x, y;
};
POINT p[PMAX];
int h[PMAX];
int sgn(double arg) {
if(abs(arg)< eps) return 0;
if(arg < eps) return -1;
if(arg > eps) return +1;
}
double ccw(POINT a, POINT b, POINT c) {//2132
return sgn((a.x-b.x)*(c.y-b.y)-(a.y-b.y)*(c.x-b.x));
}
bool cmp(POINT a, POINT b) {
return ccw(p[0], a, b)>0;
}
int main(void) {
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
int n;
int i, ll, top;
ll = 0;
scanf("%d",&n);
for (i=0; i<n; ++i) {
scanf("%lf %lf",&p[i].x,&p[i].y);
if(p[ll].y < p[i].y || (p[ll].y==p[i].y && p[ll].x>p[i].y))
ll = i;
}
swap(p[0], p[ll]);
sort(p+1, p+n, cmp);
p[n] = p[0];
top = 1;
i = 2;
h[0] = 0;
h[1] = 1;
while(i<=n) {
if(ccw(p[h[top-1]], p[h[top]], p[i])>0)
h[++top] = i++;
else
--top;
}
printf("%d\n",top);
for(i=0; i<=top; ++i)
printf("%f %f\n",p[h[i]].x,p[h[i]].y);
return 0;
}