Pagini recente » Cod sursa (job #1759126) | Cod sursa (job #1157513) | Cod sursa (job #2859741) | Cod sursa (job #910190) | Cod sursa (job #2700494)
#include<bits/stdc++.h>
// #define int long long
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pi;
const int mod = 1e9 + 7;
const int nax = 1e3 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
struct P {
double x, y;
void read() {
in >> x >> y;
}
P operator -(const P &him) const {
return P{x - him.x, y - him.y};
}
long long operator *(const P &him) const {
return x * him.y - y * him.x;
}
void operator -=(const P &him) {
x -= him.x;
y -= him.y;
}
double triangle(const P &one, const P &two) const {
return (one - *this) * (two - *this);
}
bool operator <(const P& him) const {
return mp(x, y) < mp(him.x, him.y);
}
};
vector<P> create(vector<P> points) {
vector<P> hull;
hull.push_back(points[0]);
for(int i = 1; i < points.size(); ++i) {
while((int) hull.size() >= 2) {
P one = hull.end()[-1];
P two = hull.end()[-2];
if(two.triangle(one, points[i]) <= 0) {
break;
}
hull.pop_back();
}
hull.push_back(points[i]);
}
return hull;
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
vector<P> points;
int n;
in >> n;
for(int i = 1; i <= n; i++) {
P x;
x.read();
points.pb(x);
}
sort(points.begin(), points.end());
vector<P> upper = create(points);
reverse(points.begin(), points.end());
vector<P> bottom = create(points);
upper.pop_back();
bottom.pop_back();
out << upper.size() + bottom.size() << '\n';
out << fixed << setprecision(10);
for(int i = 0; i < upper.size(); i++) {
out << upper[i].x << ' ' << upper[i].y << '\n';
}
for(int i = 0; i < bottom.size(); i++) {
out << bottom[i].x << ' ' << bottom[i].y << '\n';
}
return 0;
}