Pagini recente » Profil chandra3223 | Cod sursa (job #1328741) | Cod sursa (job #2355608) | Cod sursa (job #3358218) | Cod sursa (job #3359333)
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
struct point {
ld x, y;
};
point pivot;
ld cross(point o, point a, point b) {
return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}
ld dist2(point a, point b) {
return (a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y);
}
bool cmp(point a, point b) {
ld cp = cross(pivot, a, b);
if (cp != 0) return cp > 0;
return dist2(pivot, a) < dist2(pivot, b);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
int n;
cin >> n;
vector<point> pts(n);
for (int i = 0; i < n; i++) {
cin >> pts[i].x >> pts[i].y;
}
int minidx = 0;
for (int i = 1; i < n; i++) {
if (pts[i].x < pts[minidx].x ||
(pts[i].x == pts[minidx].x && pts[i].y < pts[minidx].y))
minidx = i;
}
swap(pts[0], pts[minidx]);
pivot = pts[0];
sort(pts.begin() + 1, pts.end(), cmp);
vector<point> hull;
hull.push_back(pts[0]);
hull.push_back(pts[1]);
for (int i = 2; i < n; i++) {
while (hull.size() >= 2 &&
cross(hull[hull.size()-2], hull[hull.size()-1], pts[i]) <= 0)
hull.pop_back();
hull.push_back(pts[i]);
}
int h = hull.size();
cout << h << "\n";
cout << fixed << setprecision(6);
for (int i = 0; i < h; i++) {
cout << hull[i].x << " " << hull[i].y << "\n";
}
return 0;
}