Pagini recente » Cod sursa (job #1663316) | Cod sursa (job #2338658) | Cod sursa (job #2901013) | Cod sursa (job #1522954) | Cod sursa (job #2539726)
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
int n, top;
long double x = 2e9, y = 2e9;
struct idk {
long double x, y;
} stiva[120005], a[120005];
bool semn(idk x1, idk x2, idk x3) {
long double ans = (x1.x - x2.x) * (x1.y - x3.y) - (x1.y - x2.y) * (x1.x - x3.x);
return (ans > 0);
}
bool cmp(idk _x, idk _y) {
return semn({0, 0}, _x, _y);
}
int main() {
fin >> n;
for (int i = 1; i <= n; ++i) {
fin >> a[i].x >> a[i].y;
if (a[i].y <= y) {
if (a[i].y == y && a[i].x < x)
x = a[i].x;
else if (a[i].y < y) {
y = a[i].y;
x = a[i].x;
}
}
}
for (int i = 1; i <= n; ++i) {
a[i].x -= x;
a[i].y -= y;
if (a[i].x == 0 && a[i].y == 0)
swap(a[1], a[i]);
}
sort (a + 2, a + n + 1, cmp);
stiva[++top] = a[1];
stiva[++top] = a[2];
for (int i = 3; i <= n; ++i) {
while (top >= 2 && !semn(stiva[top - 1], stiva[top], a[i]))
--top;
stiva[++top] = a[i];
}
fout << top << '\n';
fout << fixed << setprecision(12);
for (int i = 1; i <= top; ++i)
fout << stiva[i].x + x << ' ' << stiva[i].y + y << '\n';
return 0;
}