Pagini recente » Cod sursa (job #2970081) | Cod sursa (job #1898065) | Cod sursa (job #1306647) | Cod sursa (job #3291788) | Cod sursa (job #3248191)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int MAX_SIZE = 120000;
int stk[MAX_SIZE + 1];
struct date {
double x, y;
int parte; //de clarificat
} v[MAX_SIZE + 1], first, last;
bool comp(date first, date second) {
if (first.x < second.x) {
return true;
}
if (first.x > second.x) {
return false;
}
if (first.y < second.y) {
return true;
}
if (first.y > second.y) {
return false;
}
return false;
}
double arie(date a, date b, date c) {
return a.x * b.y + b.x * c.y + c.x * a.y - b.y * c.x - c.y * a.x - a.y * b.x;
}
int main() {
int n;
fin >> n;
for (int i = 1; i <= n; ++i) {
fin >> v[i].x >> v[i].y;
}
sort(v + 1, v + n + 1, comp);
first = v[1];
last = v[n];
for (int i = 2; i < n; ++i) { // pana la n - 1
if (arie(first, last, v[i]) < 0) {
v[i].parte = 1;
} else {
v[i].parte = 2;
}
}
stk[1] = 1;
int k = 1;
for (int i = 2; i <= n; ++i) {
if (v[i].parte == 1 || v[i].parte == 0) {
while (k > 1 && arie(v[stk[k - 1]], v[stk[k]], v[i]) < 0) {
--k;
}
++k;
stk[k] = i;
}
}
int copy_k = k;
stk[k] = n;
for (int i = n - 1; i >= 1; --i) {
if (v[i].parte == 2 || v[i].parte == 0) {
while (k > copy_k && arie(v[stk[k - 1]], v[stk[k]], v[i]) < 0) {
--k;
}
++k;
stk[k] = i;
}
}
fout << k - 1 << '\n';
for (int i = 1; i < k; ++i) {
fout << fixed << setprecision(6) << v[stk[i]].x << ' ' << v[stk[i]].y << '\n';
}
return 0;
}