Pagini recente » Cod sursa (job #1518949) | Cod sursa (job #2563338) | Cod sursa (job #797687) | Cod sursa (job #3216232) | Cod sursa (job #2566543)
#include <bits/stdc++.h>
#define rational long double
#define point std::pair <rational, rational>
#define EPS 1e-10
#define x first
#define y second
int N;
std::vector <point> V;
std::vector <int> hull;
rational crossproduct(const point &A, const point &B, const point &C) {
return (B.x-A.x)*(C.y-A.y) - (C.x-A.x)*(B.y-A.y);
}
bool cmp(point &A, point &B) {
return crossproduct(V[0], A, B) < EPS;
}
void computeHull() {
int minidx = 0;
for (int i=1; i<N; ++i)
if (V[i] < V[minidx])
minidx = i;
std:;swap(V[0], V[minidx]);
std::sort(V.begin()+1, V.end(), cmp);
hull.push_back(0);
hull.push_back(1);
for (int i=2; i<N; ++i) {
while (hull.size() >= 2 && crossproduct(V[hull[hull.size()-2]], V[hull.back()], V[i]) > EPS)
hull.pop_back();
hull.push_back(i);
}
}
#define FILENAME std::string("infasuratoare")
std::ifstream input (FILENAME+".in");
std::ofstream output(FILENAME+".out");
int main()
{
input >> N;
V.resize(N);
for (auto &it:V) input >> it.first >> it.second;
computeHull();
output << hull.size() << '\n';
output << std::fixed << std::setprecision(6);
for (int i=0; i<hull.size(); ++i)
output << V[hull[i]].first << ' ' << V[hull[i]].second << '\n';
return 0;
}