Pagini recente » Cod sursa (job #1882548) | Statistici Raileanu Alexandru (Alex1241341324) | Cod sursa (job #2272753) | Cod sursa (job #1495145) | Cod sursa (job #1174874)
#include<fstream>
#include<cstdlib>
#include<iomanip>
using namespace std;
struct Punct {
double x, y;
};
Punct v[120001], pmin;
int st[120002], imin;
int n;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
void afla_min() {
int i;
pmin.x = v[0].x;
pmin.y = v[0].y;
imin = 0;
for(i = 1; i < n; i++) {
if(v[i].y < pmin.y) {
pmin.x = v[i].x;
pmin.y = v[i].y;
imin = i;
} else {
if(v[i].y == pmin.y && v[i].x < pmin.x) {
pmin.x = v[i].x;
imin = i;
}
}
}
}
// calculeaza valoarea pe axa Z a produsului vectorial dintre AB si BC
double cross(Punct a, Punct b, Punct c) {
double det;
det = (b.x - a.x) * (c.y - b.y) - (b.y - a.y) * (c.x - b.x);
return det;
}
int compar(const void *a, const void *b) {
Punct pa = *(Punct *)a;
Punct pb = *(Punct *)b;
return (cross(pmin, pa, pb) > 0) ? -1 : 1;
}
void infasuratoare() {
int i;
st[++st[0]] = 0;
st[++st[0]] = 1;
for(i = 2; i < n; i++) {
st[++st[0]] = i;
// cat timp am in stiva mai mult de 2 puncte si ultimele 3 formeaza un nod exterior, elimina-l pe cel din mijloc
while(st[0] > 2 && cross(v[st[st[0]-2]], v[st[st[0]-1]], v[st[st[0]]]) < 0) {
st[st[0]-1] = st[st[0]];
st[0]--;
}
}
}
int main() {
int i;
Punct aux;
fin >> n;
for(i = 0; i < n; i++) {
fin >> v[i].x >> v[i].y;
}
afla_min();
// pune punctul minim pe prima pozitie
aux = v[0];
v[0] = v[imin];
v[imin] = aux;
// sorteaza restul de n-1 puncte dupa unghiul pe care il fac cu v[0]
qsort(v+1, n-1, sizeof(Punct), compar);
v[n++] = v[0];
infasuratoare();
fout << st[0]-1 << "\n";
fout << setprecision(6);
fout << fixed;
for(i = 1; i < st[0]; i++) {
fout << v[st[i]].x << " " << v[st[i]].y << "\n";
}
return 0;
}