Pagini recente » Cod sursa (job #3295197) | Cod sursa (job #3230376) | Cod sursa (job #3230164) | Cod sursa (job #1108563) | Cod sursa (job #3298858)
#include <bits/stdc++.h>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
struct ura
{
double x,y;
bool poz;
};
ura v[120005];
bool cmp(ura a, ura b)
{
if(a.x<b.x)
return true;
else if(a.x==b.x&&a.y<b.y)
return true;
return false;
}
float calc(ura a, ura b, ura c)
{
return (a.x*b.y+b.x*c.y+c.x*a.y-b.y*c.x-c.y*a.x-a.y*b.x);
}
vector<ura> st;
int main()
{
int n;
in>>n;
for(int i=1;i<=n;i++)
in>>v[i].x>>v[i].y;
sort(v+1,v+n+1,cmp);
for(int i=1;i<=n;i++)
v[i].poz=(calc(v[1],v[n],v[i])>0);
//cout<<v[1].poz<<" "<<calc(v[1],v[n],v[i]);
st.push_back(v[1]);
for(int i=2;i<=n;i++)
{
int ari=calc(v[1],v[n],v[i]);
if(v[i].poz)
continue;
if(st.size()==1)
st.push_back(v[i]);
else
{
while(st.size()>=2&&calc(st[st.size()-2],v[i],st[st.size()-1])>0)
st.pop_back();
st.push_back(v[i]);
}
}
int ckc=st.size();
v[1].poz=1;
for(int i=n;i>=1;i--)
{
int ari=calc(v[1],v[n],v[i]);
if(!v[i].poz)
continue;
if(st.size()==ckc)
st.push_back(v[i]);
else
{
while(st.size()-ckc>=1&&calc(st[st.size()-2],v[i],st[st.size()-1])>0)
st.pop_back();
st.push_back(v[i]);
}
//cout<<st.size()<<" ";
}
st.pop_back();
out<<st.size()<<"\n";
out<<fixed<<setprecision(12);
for(int i=0;i<st.size();i++)
out<<st[i].x<<" "<<st[i].y<<"\n";
return 0;
}