Pagini recente » Cod sursa (job #2961819) | Cod sursa (job #878086) | Cod sursa (job #2446362) | Cod sursa (job #3124623) | Cod sursa (job #2156290)
#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#include <fstream>
#include <iomanip>
using namespace std;
struct poz{
double x,y;
bool operator<(poz aux){
if(aux.x==x)
return aux.y<y;
return aux.x<x;
}
};
class stiva:public stack<poz>{
public :
poz top_l(){
poz aux,aux2;
aux=top();
pop();
aux2=top();
push(aux);
return aux2;
}
};
stiva st;
bool semnarie(poz p1,poz p2,poz p3){
return (p2.x*p1.y+p3.x*p2.y+p1.x*p3.y-p1.x*p2.y-p2.x*p3.y-p3.x*p1.y)>0;
}
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
vector<poz>v;
vector<poz>v2;
void infasuratoare1( ){
for(int i=0;i <v.size();i++){
while(st.size()>1 && semnarie(st.top(),st.top_l(),v[i]))
st.pop();
st.push(v[i]);
}
while(st.size()>1)
v2.push_back(st.top()),st.pop();
st.pop();
for(int i=v.size()-1;i>=0;i--){
while(st.size()>1&& semnarie(st.top(),st.top_l(),v[i]))
st.pop();
st.push(v[i]);
}
while(st.size()>1)
v2.push_back(st.top()),st.pop();
st.pop();
}
int main()
{
int n;
double aux1,aux2;
in>>n;
for(int i=1;i<=n;i++){
in>>aux1>>aux2;
v.push_back((poz){aux1,aux2});
}
sort(v.begin(),v.end());
infasuratoare1();
out<<v2.size()<<"\n";
for(int i=0;i<v2.size();i++)
out<<fixed<<setprecision(12)<<v2[i].x<<" "<<v2[i].y<<"\n";
return 0;
}