Pagini recente » Cod sursa (job #2855146) | Cod sursa (job #1564838) | Cod sursa (job #1616327) | Cod sursa (job #3132176) | Cod sursa (job #2874609)
#include <bits/stdc++.h>
using namespace std;
#define int long long
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
struct point {
double x, y;
void read() {
in >> x >> y;
}
void write() {
out << fixed << setprecision(12) << x << ' ' << y << '\n';
}
point operator - (const point &B) const {
return point{x - B.x, y - B.y};
}
void operator -= (const point &B) {
x -= B.x;
y -= B.y;
}
long double operator * (const point &B) const {
return x * B.y - y * B.x;
}
long double orientation(const point &A, const point &B) const {
return (A - *this) * (B - *this);
}
long double dist(point A) {
A -= *this;
return A.x * A.x + A.y * A.y;
}
bool operator <(const point &A) {
if(x == A.x) {
return y < A.y;
}
return x < A.x;
}
};
vector<point> buildHull(vector<point> A) {
//
vector<point> hull;
for(int i = 0; i < (int) A.size(); ++i) {
while(hull.size() >= 2) {
int sz = hull.size();
point P1 = hull[sz - 2];
point P2 = hull[sz - 1];
if(P1.orientation(P2, A[i]) < 0) {
break;
}
hull.pop_back();
}
hull.push_back(A[i]);
}
return hull;
}
int32_t main() {
int n;
in >> n;
vector<point> points(n);
for(int i = 0; i < n; ++i) {
points[i].read();
}
sort(points.begin(), points.end());
vector<point> upperHull = buildHull(points);
reverse(points.begin(), points.end());
vector<point> lowerHull = buildHull(points);
reverse(lowerHull.begin(), lowerHull.end());
reverse(upperHull.begin(), upperHull.end());
lowerHull.pop_back();
upperHull.pop_back();
out << upperHull.size() + lowerHull.size() << '\n';
for(auto it : lowerHull) {
it.write();
}
for(auto it : upperHull) {
it.write();
}
}