Pagini recente » Cod sursa (job #159865) | Cod sursa (job #774457) | Cod sursa (job #2526115) | Cod sursa (job #1155599) | Cod sursa (job #2369410)
#include <bits/stdc++.h>
#define ldb long double
#define ldb_pair std::pair <long double, long double>
#define x first
#define y second
#define eps 1e-12
inline ldb crossproduct(const ldb_pair& p0, const ldb_pair& p1, const ldb_pair& p2) {
return (p1.x - p0.x) * (p2.y - p0.y) - (p1.y - p0.y) * (p2.x - p0.x);
}
ldb_pair origin;
inline bool cmp(const ldb_pair& p0, const ldb_pair& p1) {
return crossproduct(origin, p0, p1) < eps;
}
std::istream& operator >> (std::istream& stream, ldb_pair& data) {
return stream >> data.first >> data.second;
}
#define MAXN 120005
int N;
ldb_pair V[MAXN];
void Sortare() {
int hullbegin = 0;
for (int i=1; i<N; ++i)
if (V[i] < V[hullbegin])
hullbegin = i;
std::swap(V[0], V[hullbegin]);
origin = V[0];
std::sort(V+1, V+N, cmp);
}
std::vector <int> Stack;
void ConvexHull() {
Stack.push_back(0);
Stack.push_back(1);
for (int i=2; i<N; ++i) {
while (Stack.size() > 1 && crossproduct(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=0; i<N; ++i)
In >> V[i];
}
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]].first << ' ' << V[Stack[i]].second << '\n';
}
int main()
{
Citire();
Rezolvare();
return 0;
}