Pagini recente » Cod sursa (job #2040587) | Cod sursa (job #1637384) | Cod sursa (job #1501210) | Cod sursa (job #1629719) | Cod sursa (job #1663615)
#include <vector>
#include <fstream>
#include <iomanip>
#include <algorithm>
using namespace std;
typedef struct sPoint
{
double x;
double y;
} Point;
// Global variable
bool OrderAsc(const Point& A, const Point& B)
{
return A.x < B.x || (A.x == B.x && A.y < B.y);
}
void LoadData(const char* filePath, vector<Point>& points)
{
ifstream f(filePath);
int n;
f >> n;
for (int i = 1; i <= n; ++i)
{
Point p;
f >> p.x >> p.y;
points.push_back(p);
}
}
void SaveData(const char* filePath, const vector<Point>& points)
{
ofstream g(filePath);
g << points.size() << "\n";
g << setprecision(6) << fixed;
for (auto p : points)
{
g << p.x << " " << p.y << " \n";
}
}
double CrossProduct(const Point& O, const Point& A, const Point& B)
{
return (long)(A.x - O.x) * (B.y - O.y) - (long)(A.y - O.y) * (B.x - O.x);
}
void Process(vector<Point>& points, vector<Point>& outPoints)
{
sort(points.begin(), points.end(), OrderAsc);
size_t size = points.size();
size_t hullSize = 0;
for (size_t i = 0; i < size; i++)
{
hullSize = outPoints.size();
while (hullSize >= 2 && CrossProduct(outPoints[hullSize - 2], outPoints[hullSize - 1], points[i]) <= 0)
{
outPoints.erase(outPoints.end()-1);
hullSize--;
}
outPoints.push_back(points[i]);
}
outPoints.erase(outPoints.end() - 1);
const size_t lowerSize = outPoints.size();
for (size_t i = size - 1; i > 0; i--)
{
hullSize = outPoints.size();
while (hullSize - lowerSize >= 2 && CrossProduct(outPoints[hullSize - 2], outPoints[hullSize - 1], points[i]) <= 0)
{
outPoints.erase(outPoints.end()-1);
hullSize--;
}
outPoints.push_back(points[i]);
}
}
int main()
{
vector<Point> points;
vector<Point> hull;
LoadData("infasuratoare.in", points);
Process(points, hull);
SaveData("infasuratoare.out", hull);
return 0;
}