Pagini recente » Cod sursa (job #2955467) | Rating ShikaMona (ramona93) | Cod sursa (job #1401392) | Cod sursa (job #2308334) | Cod sursa (job #2740298)
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
struct p {
long double x, y;
p operator- (p b) {
return p{x - b.x, y - b.y};
}
void operator-= (p b) {
x -= b.x;
y -= b.y;
}
long double operator* (p b) {
return 1LL * x * b.y - 1LL * y * b.x;
}
long double triangle (p b, p c) {
return (b - *this) * (c - *this);
}
};
int n;
vector<p> points;
vector<p> hull;
void read() {
int i;
ifstream f("infasuratoare.in");
f >> n;
points.resize(n);
for (i = 1; i <= n; i++)
f >> points[i - 1].x >> points[i - 1].y;
}
bool csort(p a, p b) {
if (a.x < b.x)
return 1;
return 0;
}
void solve() {
int i, size, times;
p a, b;
sort(points.begin(), points.end(), csort);
for (times = 0; times < 2; times++) {
size = hull.size();
for (i = 0; i < n; i++) {
while (hull.size() - size >= 2) {
a = hull.end()[-2];
b = hull.end()[-1];
if (a.triangle(b, points[i]) <= 0)
break;
hull.pop_back();
}
hull.emplace_back(points[i]);
}
hull.pop_back();
reverse(points.begin(), points.end());
}
}
void output() {
ofstream g("infasuratoare.out");
g << hull.size() << '\n';
int i;
for (i = hull.size() - 1; i >= 0; i--)
g << setprecision(12) << fixed << hull[i].x << ' ' << hull[i].y << '\n';
g.close();
}
int main() {
read();
solve();
output();
return 0;
}