Cod sursa(job #377346)

Utilizator Bogdan_tmmTirca Bogdan Bogdan_tmm Data 24 decembrie 2009 02:57:42
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
typedef pair <double,double> p;
int n;
vector <p> a;
class stack
{
public:
	vector <p> st;
	void pb(p x)
	{
		st.push_back(x);
	}
	void pop()
	{
		st.pop_back();
	}
	p last()
	{
		return st.back();
	}
	p last2()
	{
		return st[st.size()-2];
	}
	void Print()
	{
		printf("%d\n",(int)st.size());
		for(int i=0;i<(int)st.size();i++)
			printf("%lf %lf\n",st[i].first,st[i].second);
	}
};
bool cmp(p x,p y)
{
	return (y.first-a.begin()->first)*(x.second-a.begin()->second)<(x.first-a.begin()->first)*(y.second-a.begin()->second);
}
double prod(p x,p y,p z)
{
	return  (z.first-x.first)*(y.second-x.second)-(y.first-x.first)*(z.second-x.second);
}
int main()
{
	freopen("infasuratoare.in","r",stdin);
	freopen("infasuratoare.out","w",stdout);
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		p x;
		scanf("%lf%lf",&x.first,&x.second);
		a.push_back(x);
	}
	vector <p> ::iterator it =a.begin()+1,min=a.begin();
	for(;it!=a.end();it++)
		if(it->first<min->first||it->first==min->first&&it->second<min->second)
			min=it;
	swap(*a.begin(),*min);
	stable_sort(a.begin()+1,a.end(),cmp);
	stack st;
	st.pb(*a.begin());st.pb(*(a.begin()+1));st.pb(*(a.begin()+2));
	it=a.begin()+3;
	while(it!=a.end())
	{
		while(prod(st.last2(),st.last(),*it)>=0)
			st.pop();
		st.pb(*it++);
	}
	st.Print();
	return 0;
}