Pagini recente » Cod sursa (job #2968776) | Cod sursa (job #2951134) | Cod sursa (job #1579766) | Cod sursa (job #1691849) | Cod sursa (job #451763)
Cod sursa(job #451763)
# include <cstdio>
# include <algorithm>
using namespace std;
# define FIN "infasuratoare.in"
# define FOUT "infasuratoare.out"
# define x first
# define y second
# define MAX_N 120005
int Stack[MAX_N];
int N, i, j, vf;
pair <double, double> Pol[MAX_N];
int cmp1(pair <double, double> A, pair <double, double> B) {
return (A.y - Pol[1].y) * (B.x - Pol[1].x) < (B.y - Pol[1].y) * (A.x - Pol[1].x);
}
int cmp2(pair <double, double> A, pair <double, double> B) {
return A.y > B.y;
}
int parte(int i, int j, int k) {
return ((Pol[i].x - Pol[k].x) * (Pol[j].y - Pol[k].y) - (Pol[i].y - Pol[k].y) * (Pol[j].x - Pol[k].x) > 0);
}
void convex() {
int i, j, bnd, pleft;
pleft = 1;
for (i = 1; i <= N; ++i)
if ((Pol[pleft].x == Pol[i].x && Pol[pleft].y > Pol[i].y) || Pol[pleft].x > Pol[i].x) pleft = i;
pair <double, double> aux = Pol[pleft]; Pol[pleft] = Pol[1]; Pol[1] = aux;
i = 2; j = N;
while (i <= j) {
while (Pol[i].x != Pol[1].x && i <= N) ++i;
while (Pol[j].x == Pol[1].x && j >= 2) --j;
if (i < j)
aux = Pol[i], Pol[i] = Pol[j], Pol[j] = aux;
}
for (bnd = 2; bnd <= N && Pol[bnd].x != Pol[1].x; ++bnd);
sort(Pol + 2, Pol + bnd, cmp1);
if (bnd <= N) sort(Pol + bnd + 1, Pol + N + 1, cmp2);
//for (i = 1; i <= N; ++i) printf("%lf %lf\n", Pol[i].x, Pol[i].y);
--bnd; Stack[vf = 1] = 1;
for (i = 2; i <= N; ++i) {
if (vf < 2) {
Stack[++vf] = i;
continue;
}
while (vf >= 2 && !parte(Stack[vf - 1], Stack[vf], i)) --vf;
Stack[++vf] = i;
}
}
int main() {
freopen(FIN, "r", stdin);
freopen(FOUT, "w", stdout);
scanf("%d", &N);
for (i = 1; i <= N; ++i) scanf("%lf%lf", &Pol[i].x, &Pol[i].y);
convex();
printf("%d\n", vf);
for (i = 1; i <= vf; ++i) printf("%lf %lf\n", Pol[Stack[i]].x, Pol[Stack[i]].y);
return 0;
}