Cod sursa(job #1663615)

Utilizator mrazvanRazvan Mititelu mrazvan Data 26 martie 2016 10:17:52
Problema Infasuratoare convexa Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.86 kb
#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;
}