Pagini recente » Cod sursa (job #2107436) | Cod sursa (job #499548) | Cod sursa (job #1583153) | Cod sursa (job #956021) | Cod sursa (job #2890785)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
// ^
// |
// |y
// ------> x
const double EPS = 1e-12;
struct Dot
{
double x;
double y;
inline Dot operator- (const Dot& a) const
{
Dot result;
result.x = x - a.x;
result.y = y - a.y;
return result;
}
};
inline bool LessThan(const double& a, const double& b) {
return (a - b < -EPS);
}
inline bool GreaterThan(const double& a, const double& b) {
return (a - b > EPS);
}
inline bool Equals(const double a, const double b) {
return (a - b < EPS && a - b > -EPS);
}
int n;
vector <Dot> dots;
vector <Dot> convexHull;
double CrossProduct(const Dot& a, const Dot& b)
{
return (a.x * b.y) - (a.y * b.x);
}
bool cmp(const Dot& a, const Dot& b) {
return LessThan(CrossProduct(a - dots[0], b - dots[0]), 0);
}
int GetPivotPoint() {
Dot bestPivot = {0x3f3f3f3f, 0x3f3f3f3f};
int index = -1;
for (int i = 0; i < n; i++)
{
if (LessThan(dots[i].x, bestPivot.x) ||
(Equals(dots[i].x, bestPivot.x) && LessThan(dots[i].y, bestPivot.y))) {
bestPivot = dots[i];
index = i;
}
}
return index;
}
void GenerateConvexHull()
{
convexHull.push_back(dots[0]);
convexHull.push_back(dots[1]);
for (int currIdx = 2; currIdx < n; currIdx++)
{
Dot lastVec = convexHull[convexHull.size() - 2] - convexHull[convexHull.size() - 1];
Dot currDot = dots[currIdx];
Dot currVec = convexHull[convexHull.size() - 2] - currDot;
while (GreaterThan(CrossProduct(lastVec, currVec), 0))
{
convexHull.pop_back();
lastVec = convexHull[convexHull.size() - 2] - convexHull[convexHull.size() - 1];
currDot = dots[currIdx];
currVec = convexHull[convexHull.size() - 2] - currDot;
}
convexHull.push_back(currDot);
}
}
int main() {
fin >> n;
for (int i = 1; i <= n; i++)
{
double x, y;
fin >> x >> y;
dots.push_back({x, y});
}
int pivotIdx = GetPivotPoint();
swap(dots[0], dots[pivotIdx]);
sort(dots.begin() + 1, dots.end(), cmp);
GenerateConvexHull();
fout << convexHull.size() << '\n';
fout << fixed << setprecision(12);
std::for_each(convexHull.rbegin(), convexHull.rend(), [](const Dot& currDot){
fout << currDot.x << ' ' << currDot.y << '\n';
});
}