Pagini recente » Cod sursa (job #825255) | Cod sursa (job #1744157) | Cod sursa (job #2320529) | Cod sursa (job #2857119) | Cod sursa (job #1266139)
#include <fstream>
#include <iomanip>
#include <vector>
#include <algorithm>
using namespace std;
const int kMaxN = 120005;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int N;
struct Point {
double x, y;
} p[kMaxN];
vector<int> ch;
double Area(const Point &p1, const Point &p2, const Point &p3) {
return p1.x * p2.y - p1.y * p2.x +
p2.x * p3.y - p2.y * p3.x +
p3.x * p1.y - p3.y * p1.x;
}
bool Compare(const Point &p1, const Point &p2) {
return Area(p[0], p1, p2) > 0;
}
int main() {
fin >> N;
for (int i = 0; i < N; ++i) {
fin >> p[i].x >> p[i].y;
if (p[i].x < p[0].x)
swap(p[0], p[i]);
}
sort(p + 1, p + N, Compare);
ch.push_back(0);
for (int i = 1; i < N; ++i) {
while (ch.size() > 1 && Area(p[ch[ch.size() - 2]], p[ch[ch.size() - 1]], p[i]) <= 0)
ch.pop_back();
ch.push_back(i);
}
fout << ch.size() << "\n" << setprecision(12) << fixed;
for (int i : ch)
fout << p[i].x << " " << p[i].y << "\n";
return 0;
}