Pagini recente » Cod sursa (job #244521) | Cod sursa (job #1955077) | Cod sursa (job #3212667) | Cod sursa (job #2757410) | Cod sursa (job #680604)
Cod sursa(job #680604)
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
struct punct{double x,y;} aux;
int n,x,y;
vector<punct> p,st;
bool cmp(const punct &a, const punct &b)
{if(a.x<b.x) return true;
if(a.x>b.x) return false;
if(a.y<b.y) return true;
if(a.y>b.y) return false;
return true;
}
bool semn(const punct &a,const punct &b, const punct &c)
{double A=b.x*c.y+c.x*a.y+a.x*b.y;
double B=-a.x*c.y-b.x*a.y-c.x*b.y;
return (A+B)<0.0;
}
int main()
{freopen("infasuratoare.in","rt",stdin);
freopen("infasuratoare.out","wt",stdout);
for(scanf("%d",&n); n; --n) scanf("%lf%lf",&x,&y),p.push_back((punct){x,y});
sort(p.begin(),p.end(),cmp);
st.push_back(p[0]); st.push_back(p[1]);
for(unsigned int i=2; i<p.size(); ++i)
{for(;st.size()>1 && semn(st[st.size()-2],st[st.size()-1],p[i]); st.pop_back());
st.push_back(p[i]);
}
for(unsigned int i=p.size(); i>0 ; --i)
{for(;st.size()>1 && semn(st[st.size()-2],st[st.size()-1],p[i]); st.pop_back());
st.push_back(p[i]);
}
st.pop_back();
printf("%d\n",st.size());
for(unsigned int i=0; i<st.size(); ++i)
printf("%0.6lf %0.6lf\n",st[i].x,st[i].y);
return 0;
}