Pagini recente » Cod sursa (job #1123392) | Cod sursa (job #768080) | Cod sursa (job #2182587) | Cod sursa (job #1353125) | Cod sursa (job #1398973)
#include <iostream>
#include <algorithm>
#include <vector>
#include <fstream>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct point {
double x, y;
bool operator < (point &a, point &b) {
if (a.x == b.x)
return a.y < b.y;
return a.x < b.x;
}
};
const int MAXN = 120001;
int n;
point v[MAXN + 10];
vector<int> top, bottom;
double cross (point a, point b, point c) {
return a.x * b.y + b.x * c.y + c.x * a.y - c.x * b.y - b.x * a.y - a.x * c.y;
}
int main() {
fin >> n;
for (int i = 1; i <= n; ++i)
fin >> v[i].x >> v[i].y;
sort(v + 1, v + n + 1);
for (int i = 1; i <= n; ++i) {
while (top.size() >= 2 && cross(*(top.end() - 1), *(top.end() - 2), v[i]) <= 0)
top.pop_back();
top.push_back(v[i]);
}
for (int i = n; i >= 0; --i) {
while (bottom.size() >= 2 && cross(*(bottom.end() - 1), *(bottom.end() - 2), v[i]) <= 0)
bottom.pop_back();
bottom.push_back(v[i]);
}
fout << top.size() + bottom.size() << "\n";
for (auto it: top)
fout << it.x << " " << it.y << "\n";
for (auto it: bottom)
fout << it.x << " " << it.y << "\n";
return 0;
}