Pagini recente » Cod sursa (job #2298581) | Cod sursa (job #1514677) | Cod sursa (job #2315430) | Cod sursa (job #1040385) | Cod sursa (job #2044403)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int NMAX = 120005;
struct punct {
double x, y;
};
int n;
punct vec[NMAX];
int st[NMAX], top;
bool seen[NMAX]; // seen[i] = true, daca i este pe stiva
void read() {
fin >> n;
for (int i = 1; i <= n; ++ i)
fin >> vec[i].x >> vec[i].y;
}
double F(int i, int j, int p) {
// returneaza < 0 daca puncdtul vec[p] este in semiplanul - al dreptei determinata de puctele (vec[i], vec[j])
return vec[p].x * (vec[i].y - vec[j].y) + vec[p].y * (vec[j].x - vec[i].x) + vec[i].x * vec[j].y - vec[j].x * vec[i].y;
}
inline bool cmp(punct A, punct B) {
if (A.y == B.y)
return A.x < B.x;
return A.y < B.y;
}
void hill() {
// algoritmul lui Hill
sort(vec + 1, vec + n + 1, cmp);
st[++ top] = 1;
st[++ top] = 2;
seen[2] = true;
for (int i = 3; i <= n; ++ i) {
while (top > 1 && F(st[top - 1], st[top], i) < 0) {
seen[st[top]] = false;
-- top;
}
st[++ top] = i;
seen[i] = true;
}
for (int i = n - 1; i; -- i)
if (!seen[i]) {
while (F(st[top - 1], st[top], i) < 0) {
seen[st[top]] = false;
-- top;
}
st[++ top] = i;
seen[i] = true;
}
}
void print() {
fout << top - 1 << "\n";
for (int i = 1; i < top; ++ i)
fout << fixed << setprecision(12) << vec[st[i]].x << " " << vec[st[i]].y << "\n";
}
int main() {
read();
fin.close();
hill();
print();
fout.close();
return 0;
}