Pagini recente » Cod sursa (job #2113361) | Cod sursa (job #492141) | Cod sursa (job #2526674) | Cod sursa (job #403580) | Cod sursa (job #2539673)
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
int n, top;
double x = 2e9, y = 2e9;
struct idk {
double x, y;
} stiva[120005], a[120005];
bool cmp(idk _x, idk _y) {
double x1 = _x.y / _x.x;
double x2 = _y.y / _y.x;
if (x1 < 0 && x2 < 0)
return (x1 < x2);
if (x1 > 0 && x2 > 0)
return (x1 < x2);
if (x1 >= 0 && x2 < 0)
return true;
return false;
}
bool semn(idk x1, idk x2, idk x3) {
int ans = (x1.x - x2.x) * (x1.y - x3.y) - (x1.y - x2.y) * (x1.x - x3.x);
return (ans > 0);
}
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;
}
sort (a + 1, a + n + 1, cmp);
stiva[++top] = a[1];
stiva[++top] = a[2];
stiva[++top] = a[3];
for (int i = 3; i <= n; ++i) {
while (top >= 3 && semn(stiva[top - 2], stiva[top - 1], stiva[top]) != 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;
}