Pagini recente » Cod sursa (job #257971) | Cod sursa (job #2692197) | Cod sursa (job #1147119) | Cod sursa (job #910646) | Cod sursa (job #2376254)
#include <bits/stdc++.h>
#define ldb long double
#define ldb_pair std::pair <ldb, ldb>
#define x first
#define y second
#define EPS (1e-12)
ldb cross_product(const ldb_pair& A, const ldb_pair& B, const ldb_pair& C) {
return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}
ldb_pair origin;
inline bool cmp(const ldb_pair& p0, const ldb_pair& p1) {
return cross_product(origin, p0, p1) < EPS;
}
#define MAXN 120005
int N;
ldb_pair V[MAXN];
void Sortare() {
int hull_begin = 1;
for (int i=2; i<=N; ++i)
if (V[i] < V[hull_begin])
hull_begin = i;
std::swap(V[1], V[hull_begin]);
origin = V[1];
std::sort(V+2, V+N+1, cmp);
}
std::vector <int> Stack;
void ConvexHull() {
Stack.push_back(1);
Stack.push_back(2);
for (int i=3; i<=N; ++i) {
while (Stack.size() > 1 && cross_product(V[Stack[Stack.size()-2]], V[Stack[Stack.size()-1]], V[i]) > EPS)
Stack.pop_back();
Stack.push_back(i);
}
}
std::ifstream In ("infasuratoare.in");
std::ofstream Out("infasuratoare.out");
void Citire() {
In >> N;
for (int i=1; i<=N; ++i)
In >> V[i].x >> V[i].y;
}
void Rezolvare() {
Sortare();
ConvexHull();
Out << Stack.size() << '\n';
Out << std::fixed << std::setprecision(6);
for (int i = Stack.size()-1; i>=0; --i)
Out << V[Stack[i]].x << ' ' << V[Stack[i]].y << '\n';
}
int main()
{
Citire();
Rezolvare();
return 0;
}