Cod sursa(job #1728047)

Utilizator theo.stoicanTheodor Stoican theo.stoican Data 12 iulie 2016 09:24:58
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.65 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;
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 p1, Point p2, Point p3)
{    
	double x1 = p1.x, y1 = p1.y, x2 = p2.x, y2 = p2.y, x3 = p3.x, y3 = p3.y;
	double val = x1*y2 + x2*y3 + x3*y1 - x3*y2 - x1*y3 - x2*y1;
				if (val < 0)
					return 2;
				if (val > 0) 
					return 1;
				if (val == 0)
					return 0;
}

bool myfunction(Point p1, Point p2)
{
	int o = orientation (points[0], p1, p2);
	if (o == 2)
		return true;
	else 
		return 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);
	scanf("%d",&n);
	double xi,yi;
	points.resize(n);
	for (int i = 0; i < n; ++i)
	{
		//int xi,yi;
		//cin>>points[i].x>>points[i].y;
		scanf("%lf %lf", &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();
	}	
}