Pagini recente » Cod sursa (job #3151188) | Cod sursa (job #1853423) | Cod sursa (job #2983515) | Cod sursa (job #2636357) | Cod sursa (job #2417634)
#include <bits/stdc++.h>
#define ldb long double
#define point_data std::pair <ldb, ldb>
std::istream& operator >> (std::istream& stream, point_data& data) {
return stream >> data.first >> data.second;
}
std::ostream& operator << (std::ostream& stream, point_data data) {
return stream << data.first << ' ' << data.second;
}
#define EPS (1e-10)
#define x first
#define y second
point_data origin;
double crossProduct(const point_data& A, const point_data& B, const point_data& C) {
return (B.x - A.x)*(C.y - A.y) - (B.y - A.y)*(C.x - A.x);
}
class ConvexHull {
protected:
std::vector <point_data> *pointsArrPtr;
std::vector <int> hullPoints;
public:
ConvexHull(std::vector <point_data>& points) {
pointsArrPtr = &points;
int hullBegin = 0;
for (int i=1; i<points.size(); ++i)
if (points[i] < points[hullBegin])
hullBegin = i;
std::swap(points[0], points[hullBegin]);
origin = points[0];
std::sort(points.begin()+1, points.end(), [](const point_data& p0, const point_data& p1)->bool {
return crossProduct(origin, p0, p1) < EPS;});
hullPoints.push_back(0);
hullPoints.push_back(1);
for (int i=2; i<points.size(); ++i) {
while (hullPoints.size()>1 && crossProduct(points[hullPoints[hullPoints.size()-2]], points[hullPoints.back()], points[i]) > EPS)
hullPoints.pop_back();
hullPoints.push_back(i);
}
}
int size() {return hullPoints.size();}
point_data point(int idx) {return (*pointsArrPtr)[hullPoints[idx]];}
int operator [] (int idx) {return hullPoints[idx];}
};
int N;
std::vector <point_data> V;
std::ifstream input ("infasuratoare.in");
std::ofstream output("infasuratoare.out");
void readInput() {
input >> N;
V.resize(N);
for (auto &it:V)
input >> it;
}
void solveInput() {
ConvexHull hull(V);
output << hull.size() << '\n';
output << std::fixed << std::setprecision(6);
for (int i=0; i<hull.size(); ++i)
output << hull.point(hull.size()-i-1) << '\n';
}
int main()
{
readInput();
solveInput();
return 0;
}