Pagini recente » Cod sursa (job #2990027) | Cod sursa (job #39452) | Cod sursa (job #2507696) | Cod sursa (job #332411) | Cod sursa (job #3226994)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct Point {
double x, y;
};
int n;
vector<Point> a;
double getWay(Point A, Point B, Point C) {
return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}
bool cmp(Point A, Point B) {
return getWay(a[0], A, B) > 0;
}
void Citire() {
fin >> n;
a.resize(n);
for (int i = 0; i < n; i++)
fin >> a[i].x >> a[i].y;
}
void ConvexHull() {
int minP = 0;
for (int i = 1; i < n; i++)
if (a[i].y < a[minP].y || (a[i].y == a[minP].y && a[i].x < a[minP].x))
minP = i;
swap(a[0], a[minP]);
sort(a.begin() + 1, a.end(), cmp);
vector<int> stv;
stv.push_back(0);
stv.push_back(1);
for (int i = 2; i < n; i++) {
while (stv.size() >= 2 && getWay(a[stv[stv.size() - 2]], a[stv.back()], a[i]) <= 0)
stv.pop_back();
stv.push_back(i);
}
fout << stv.size() << "\n";
for (int i : stv)
fout << setprecision(9) << fixed << a[i].x << " " << a[i].y << "\n";
}
int main() {
Citire();
ConvexHull();
return 0;
}