Cod sursa(job #1728041)

Utilizator theo.stoicanTheodor Stoican theo.stoican Data 12 iulie 2016 09:08:49
Problema Infasuratoare convexa Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 2.55 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
#include <iomanip>
#include <cstdio>

using namespace std;

ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");

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

int n;
Point p0(0,0);
vector<Point> points(120002);
stack<Point> s;

double euclidDistance (Point p1, Point p2)
{
	return (p1.x - p2.x) * (p1.x - p2.x) +
	(p1.y - p2.y) * (p1.y - p2.y);
}

Point nextToTop (stack<Point>& s)
{
	Point p = s.top();
	s.pop();
	Point p2 = s.top();
	s.push(p);
	return p2;
}

//2 is counter-clockwise, extracted from the
//formula involving the slope
int orientation(Point p, Point q, Point r)
{
	double val = (int)((q.y - p.y) * (r.x - q.x) - 
				(q.x - p.x) * (r.y - q.y));
				if (val == 0)
					return 0;
				return (val > 0) ? 2:1;
}

bool myfunction(Point p1, Point p2)
{
	int o = orientation (p0, p1, p2);
	if (o == 0)
		return euclidDistance(p0,p1) >= euclidDistance(p1,p2);
	return (o == 2)? true:false;
}

void convexHull()
{
	//cel mai din stanga si cel mai de jos punct
	double ymin = points[0].y;
	int min = 0;
	for (int i = 1; i < n; i++)
	{
		if (points[i].y < ymin)
		{
			ymin = points[i].y;
			min = i;
		}
		else if (points[i].y == ymin && points[i].x < points[min].x)
		{
			min = i;
		}
	}
	Point p(points[min].x, points[min].y);
	points[min].x = points[0].x;
	points[min].y = points[0].y;
	points[0].x = p.x;
	points[0].y = p.y;
	p0 = points[0];
	
	sort(points.begin()+1, points.end(), myfunction);
	
	int m = n;
	/*for (int i = 1; i < points.size(); i++)
	{
		while (i < (points.size() - 1) && orientation(p0, points[i],points[i+1]) == 0)
			i++;
		points[m] = points[i];
		m++;
	}*/
	/*if (m < 3)
	{
		cout<<"cum? "<<"\n";
		return;
	}*/
//
	s.push(points[0]);
	s.push(points[1]);
	//cout<<n<<endl;
	//for (int i = 0; i < m; i++)
	//	cout<<points[i].x<<" "<<points[i].y<<endl;
	//cout<<endl;
	//s.push(points[2]);
	for (int i = 2; i < n; i++)
	{
		while ((s.size() >= 2 )&& orientation(nextToTop(s), s.top(), points[i]) != 2)
			s.pop();
		s.push(points[i]);
	}
	//cout<<s.size()<<endl;
}

int main()
{
	freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
	cin>>n;
	double xi,yi;
	points.resize(n);
	for (int i = 0; i < n; ++i)
	{
		//int xi,yi;
		cin>>points[i].x>>points[i].y;
	}
	convexHull();
	cout<<fixed;
	cout<<setprecision(9)<<s.size()<<"\n";
	while (!s.empty())
	{
		Point aux = s.top();
		cout<<aux.x<<" "<<aux.y<<"\n";
		s.pop();
	}	
}