Pagini recente » Cod sursa (job #1912842) | Cod sursa (job #1488039) | Cod sursa (job #1513634) | Cod sursa (job #2452719) | Cod sursa (job #3224039)
#include <fstream>
#include <stack>
#include <algorithm>
#include <vector>
#include <iomanip>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
struct punct
{
double x,y;
};
punct v[120001];
stack <int>st;
vector <int>r1,r2;
bool cmp(punct a,punct b)
{
if(a.x<b.x)
return true;
if(a.x==b.x and a.y<b.y)
return true;
return false;
}
double arie(int i)
{
double x1,x2,x3,y1,y2,y3;
x1=v[i].x;
y1=v[i].y;
x2=v[st.top()].x;
y2=v[st.top()].y;
int aux=st.top();
st.pop();
x3=v[st.top()].x;
y3=v[st.top()].y;
st.push(aux);
return x1*(y2-y3)+x2*(y3-y1)+x3*(y1-y2);
}
int main()
{
int n,i;
cin>>n;
for(i=1; i<=n; i++)
cin>>v[i].x>>v[i].y;
sort(v+1,v+n+1,cmp);
for(i=1; i<=n; i++)
{
while(st.size()>=2 and arie(i)>0)
st.pop();
st.push(i);
}
while(!st.empty())
{
r1.push_back(st.top());
st.pop();
}
for(i=1; i<=n; i++)
{
while(st.size()>=2 and arie(i)<0)
st.pop();
st.push(i);
}
while(!st.empty())
{
r2.push_back(st.top());
st.pop();
}
reverse(r1.begin(),r1.end());
cout<<r1.size()+r2.size()-2<<endl;
for(i=1;i<r1.size();i++)
cout<<fixed<<setprecision(6)<<v[r1[i]].x<<" "<<v[r1[i]].y<<'\n';
for(i=1;i<r2.size();i++)
cout<<fixed<<setprecision(6)<<v[r2[i]].x<<" "<<v[r2[i]].y<<'\n';
return 0;
}