Pagini recente » Cod sursa (job #1802912) | Cod sursa (job #1714140) | Istoria paginii runda/pregatire_lot2_juniori/clasament | Cod sursa (job #163374) | Cod sursa (job #1603369)
# include <bits/stdc++.h>
# define point pair < double , double >
# define x first
# define y second
# define eps 1e-12
using namespace std;
const int Nmax = 120000 + 5;
bool ok[Nmax];
int n, k, stiv[Nmax];
double X, Y;
pair <double, double> a[Nmax];
int cmp (double a, double b) {
if (a + eps < b) return -1;
if (b + eps < a) return 1;
return 0;
}
int semn (point a, point b, point c) {
return cmp (a.x * b.y + b.x * c.y + c.x * a.y - c.x * b.y - b.x * a.y - a.x * c.y, 0);
}
void sol () {
stiv[1] = 1, stiv[2] = 2, k = 2;
ok[2] = true;
int q = 1, i = 3;
while (!ok[1]) {
while (ok[i]) {
if (i == n) q *= -1;
i += q;
}
while (k >= 2 && semn (a[stiv[k - 1]], a[stiv[k]], a[i]) == -1)
ok[stiv[k--]] = false;
stiv[++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);
sol();
printf("%d\n", k - 1);
for (int i = 2; i <= k; ++i)
printf("%lf %lf\n", a[stiv[i]].x, a[stiv[i]].y);
return 0;
}