Pagini recente » Cod sursa (job #1885128) | Cod sursa (job #124499) | Cod sursa (job #273219) | Cod sursa (job #1885500) | Cod sursa (job #3219340)
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
struct punct
{
double long x,y;
}v[120005];
bool cmp(punct a,punct b)
{
if (a.x == b.x)
return a.y < b.y;
return a.x < b.x;
}
vector <punct> st;
punct rasp[120005];
int arie(punct a, punct b, punct c)
{
return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y);
}
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
cin>>v[i].x>>v[i].y;
long double S=0;
sort(v+1,v+n+1, cmp);
punct zero;
zero.x=0;
zero.y=0;
st.push_back(zero);
st.push_back(v[1]);
int k=1;
for(int i=2;i<=n;i++)
{
if(k>=2)
{
long double s=arie(st[k-1], st[k], v[i]);
while(s<0 && k>=2)
{
st.pop_back();
k--;
s=arie(st[k-1], st[k], v[i]);
}
}
st.push_back(v[i]);
k++;
}
for(int i=1;i<=k;i++)
rasp[i]=st[i];
st.clear();
int ck=k;
k=1;
st.push_back(zero);
st.push_back(v[1]);
for(int i=2;i<=n;i++)
{
if(k>=2)
{
long double s=st[k-1].x*(st[k].y-v[i].y)+st[k].x*(v[i].y-st[k-1].y)+v[i].x*(st[k-1].y-st[k].y);
while(s>0 && k>=2)
{
st.pop_back();
k--;
s=st[k-1].x*(st[k].y-v[i].y)+st[k].x*(v[i].y-st[k-1].y)+v[i].x*(st[k-1].y-st[k].y);
}
}
st.push_back(v[i]);
k++;
}
cout<<ck+k-2<<'\n';
for(int i=1;i<ck;i++)
cout<<fixed<<setprecision(12)<<rasp[i].x<<" "<<rasp[i].y<<'\n';
for(int i=k;i>=2;i--)
cout<<fixed<<setprecision(12)<<st[i].x<<" "<<st[i].y<<'\n';
return 0;
}