Cod sursa(job #953470)

Utilizator mihaiSimuSimu Mihai mihaiSimu Data 26 mai 2013 12:30:52
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.66 kb
#include <fstream>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;
/*
ax ay 1
bx by 1
cx cy 1
*/

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

int n;double x,y;
vector< pair<double,double> > points;

double area(pair<double,double> a,pair<double,double> b,pair<double,double> c){
	return a.first*b.second+c.first*a.second+b.first*c.second-c.first*b.second-b.first*a.second-a.first*c.second;
}

struct lessThanPoint{
public : bool operator()(const pair<double,double> & a, const pair<double,double> & b){
			return area(points[0],a,b)>0;
		 }
};

void printStack(stack<pair<double,double> > &st){
	if(st.size()==0) return;
	pair<double,double> aux = st.top();st.pop();
	printStack(st);
	out<<aux.first<<" "<<aux.second<<"\n";
}

int main(){

	in>>n;
	for(int i=0;i<n;i++){
		in>>x>>y;
		points.push_back(pair<double,double> (x,y));
	}
	int minIndex=0;
	for(int i=1;i<n;i++){
		if(points[i]<points[minIndex]) minIndex=i;
	}
	pair<double,double> aux = points[minIndex];
	points[minIndex]=points[0];
	points[0]=aux;

	sort(points.begin()+1,points.end(),lessThanPoint());

	stack<pair<double,double> > st;
	st.push(points[0]);
	st.push(points[1]);

	for(int i=2;i<points.size();i++){
		aux=st.top();st.pop();
		while(area(st.top(),aux,points[i])<=0){
			aux=st.top();st.pop();
		}
		st.push(aux);st.push(points[i]);
	}

	out<<st.size()<<"\n";
	/*
	for( vector<pair <double,double> >::iterator it = st.;it!=points.end();it++){
		out<<it->first<<" "<<it->second<<"\n";
	}*/
	out << setprecision(6) << fixed;
	printStack(st);
	return 0;
}