Cod sursa(job #998193)

Utilizator Cosmin1490Balan Radu Cosmin Cosmin1490 Data 16 septembrie 2013 02:12:10
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.32 kb
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <iterator>
using namespace std;

const string file = "infasuratoare";

const string infile = file + ".in";
const string outfile = file + ".out";

const int INF = 0x3f3f3f3f;


struct Point
{
	double x;
	double y;
	Point(double x = 0.0, double y = 0.0)
	{
		this->x = x;
		this->y = y;
	}
};


int start;
vector<Point> points;
int N;

bool pred(const Point& a, const Point& b)
{
	Point& z = points[0];

	double val1 = (a.y - z.y) / (a.x - z.x);
	double val2 = (b.y - z.y) / (b.x - z.x);

	if(val1 < val2)
		return true;
	if(val1 > val2)
		return false;

	if( (a.x - z.x) * (a.x - z.x) + (a.y - z.y) * (a.y - z.y) < (b.x - z.x) * (b.x - z.x) + (b.y - z.y) * (b.y - z.y))
		return true;
	return false;
}


double cross(const Point& a, const Point& b, const Point& c)
{
	return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}


int main()
{
	fstream fin(infile.c_str(), ios::in);
	fin >> N;

	points.reserve(N);

	double x, y;
	fin >> x >> y;
	points.push_back(Point(x ,y));

	for(int i = 1; i < N; i++)
	{
		fin >> x >> y;
		points.push_back(Point(x , y));
		if(points[start].x > points[i].x || (points[start].x == points[i].x && points[start].y > points[i].y ))
		{
			start = i;
		}
	}

	swap(points[0], points[start]);
	sort(points.begin() + 1, points.end(), pred);
	fin.close();

	vector<Point> hull;
	hull.reserve(N);

	for(int i = 0; i < N; i++)
	{
		while(hull.size() >= 2 && cross(hull[hull.size() - 2], hull[hull.size() - 1], points[i]) < 0)
		{
			hull.pop_back();
		}

		hull.push_back(points[i]);

	}


	fstream fout(outfile.c_str(), ios::out);
	fout << hull.size() << "\n";

	for(vector<Point>::iterator itr = hull.begin();
		itr != hull.end();
		itr++)
	{
		fout << fixed << setprecision(6) << itr->x << " " << itr->y << "\n";
	}

	fout.close();
}