Pagini recente » Cod sursa (job #442916) | Cod sursa (job #1746347) | Cod sursa (job #2434147) | Cod sursa (job #807119) | Cod sursa (job #1408247)
#include <cstdio>
#include <algorithm>
#define NMAX 120000
using namespace std;
FILE *fin, *fout;
int n, p, sum, stiva[NMAX];
bool f;
struct punct
{
double x;
double y;
double f1;
double f2;
} v[NMAX];
bool comp(punct a, punct b)
{
return (a.f1 * b.f2 < b.f1 * a.f2);
}
int main()
{
fin = freopen("infasuratoare.in", "r", stdin);
fout = freopen("infasuratoare.out", "w", stdout);
scanf("%d", &n);
for(int i = 0; i< n; i++)
{
scanf("%lf %lf", &v[i].x, &v[i].y);
if(i == 0) continue;
if(v[i].x < v[p].x) p = i;
else if(v[i].x == v[p].x)
{
if(v[i].y < v[p].y) p = i;
}
}
swap(v[p], v[0]);
for(int i = 1; i< n; i++)
{
v[i].f1 = v[i].y - v[0].y;
v[i].f2 = v[i].x - v[0].x;
}
sort(v+1, v+n, comp);
stiva[1] = 1;
p = 1;
for(int i = 2; i< n; i++)
{
f = 0;
while(p>=1 && f == 0)
{
sum = v[stiva[p-1]].x*v[stiva[p]].y + v[stiva[p]].x*v[i].y + v[i].x*v[stiva[p-1]].y - v[i].x*v[stiva[p]].y - v[stiva[p]].x*v[stiva[p-1]].y - v[stiva[p-1]].x*v[i].y;
if(sum > 0)
{
p++;
stiva[p] = i;
f = 1;
}
if(sum < 0)
{
p--;
}
}
}
printf("%d\n", p+1);
for(int i = 0; i<= p; i++) printf("%lf %lf\n", v[stiva[i]].x, v[stiva[i]].y);
fclose(fin);
fclose(fout);
return 0;
}