Pagini recente » Cod sursa (job #782302) | Cod sursa (job #2680165) | Cod sursa (job #66713) | Cod sursa (job #2977820) | Cod sursa (job #953470)
Cod sursa(job #953470)
#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;
}