Pagini recente » Cod sursa (job #1892803) | Cod sursa (job #213822) | Cod sursa (job #1363007) | Cod sursa (job #3131849) | Cod sursa (job #2740907)
#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-12;
const int Nmax = 2e5;
struct pct {
double x, y;
int pos;
};
pct v[2 * Nmax + 5];
char vaz[Nmax + 5];
vector<int> hull;
double det(pct p, pct q, pct r) {
return p.x * (q.y - r.y) + q.x * (r.y - p.y) + r.x * (p.y - q.y);
}
// 0 -> coliniare, 1 -> viraj stanga, 2 -> viraj dreapta
int viraj(pct p, pct q, pct r) {
double d = det(p, q, r);
if (abs(d) < eps) return 0;
if (d > 0) return 1;
return 2;
}
bool cmp(pct a, pct b) {
if (a.x == b.x) return a.y < b.y;
return a.x < b.x;
}
int main()
{
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
int n;
in >> n;
for (int i = 1; i <= n; ++i) {
in >> v[i].x >> v[i].y;
v[i].pos = i;
}
sort(v + 1, v + n + 1, cmp);
for (int i = 1; i < n; ++i) v[n + i] = v[n - i];
hull.push_back(1);
for (int i = 2; i < 2 * n; ++i) {
if (vaz[v[i].pos]) continue;
while (hull.size() > 1 && viraj(v[hull[hull.size() - 2]], v[hull.back()], v[i]) == 2) {
vaz[v[hull.back()].pos] = 0;
hull.pop_back();
}
hull.push_back(i);
vaz[v[i].pos] = 1;
}
hull.pop_back();
out << hull.size() << "\n";
out << setprecision(10) << fixed;
for (int p : hull) out << v[p].x << " " << v[p].y << "\n";
return 0;
}