Pagini recente » Cod sursa (job #153101) | Cod sursa (job #2037603) | Cod sursa (job #1765112) | Cod sursa (job #1924090) | Cod sursa (job #2118518)
#include <cstdio>
#include <algorithm>
#define EPS (1e-12)
#define MAXN 120002
using namespace std;
int n, k;
struct point{
double x, y;
bool operator < (const point &aux) const {
if(x == aux.x)
return (y < aux.y);
return (x < aux.x);
}
}v[MAXN], stk[MAXN];
inline double area(const point &a, const point &b, const point &c){
return a.x*b.y - b.x*a.y + b.x*c.y - c.x*b.y + c.x*a.y - a.x*c.y;
}
bool compare(const point &a, const point &b){
return area(v[1], a, b) > 0;
}
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
int i, pos;
scanf("%d", &n);
for(i=1; i<=n; ++i)
scanf("%lf%lf", &v[i].x, &v[i].y);
pos = 1;
for(i=2; i<=n; ++i)
if(v[i] < v[pos])
pos = i;
swap(v[1], v[pos]);
sort(v+2, v+n+1, compare);
stk[1] = v[1];
stk[2] = v[2];
k = 2;
for(i=3; i<=n; ++i)
{
while(k > 2 && area(stk[k-1], stk[k], v[i]) < 0)
k--;
stk[++k] = v[i];
}
printf("%d\n", k);
for(i=1; i<=k; ++i)
printf("%.6lf %.6lf\n", stk[i].x, stk[i].y);
return 0;
}