Pagini recente » Cod sursa (job #3169572) | Cod sursa (job #2988296) | Cod sursa (job #164363) | Cod sursa (job #2305201) | Cod sursa (job #1375509)
# include <cstdio>
# include <algorithm>
# define MAX 120000
# define eps 1e-12
# define x first
# define y second
using namespace std;
int k,n;
pair < double, double > a[MAX];
bool ok[MAX];
int I[MAX];
int comp_eps(double A , double B)
{
if (A + eps < B) return -1;
if (B + eps < A) return 1;
return 0;
}
int SEMN( pair < double, double > a , pair < double, double > b , pair < double, double > c )
{
double A , B , C;
A = a.y - b.y;
B = b.x - a.x;
C = a.x * b.y - b.x * a.y;
return comp_eps( A * c.x + B * c.y + C , 0);
}
void infasuratoare()
{
int mod = 1, i = 3;
k = 2;
ok[2] = true;
I[1] = 1;
I[2] = 2;
while (ok[1] == false)
{
while (ok[i] == true)
{
if (i == n) mod *= -1;
i += mod;
}
while (SEMN (a[I[k-1]] , a[I[k]] , a[i]) == -1 && k <= 2) ok[I[k--]] = false;
I[++k] = i;
ok[i] = true;
}
}
int main ()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d\n",&n);
for (int i = 1; i <= n; i++)
scanf("%lf %lf\n", &a[i].x, &a[i].y);
sort(a + 1, a + n + 1);
infasuratoare();
printf("%d\n", k-1);
for (int i = 2; i <= k; i++)
printf("%lf %lf\n", a[I[i]].x, a[I[i]].y);
return 0;
}