Pagini recente » Cod sursa (job #2220493) | Cod sursa (job #2220498) | Cod sursa (job #2220497) | Cod sursa (job #2220507) | Cod sursa (job #2166608)
#include <fstream>
#include <iomanip>
#include <algorithm>
#define x first
#define y second
using namespace std;
ifstream f ("infasuratoare.in");
ofstream g ("infasuratoare.out");
int n,mipoz,st[120005],vf;
typedef pair <double,double> usu;
usu p[120010];
inline long double det(const usu &t1,const usu &t2,const usu &t3)
{
return t1.x*t2.y+t2.x*t3.y+t3.x*t1.y-t3.x*t2.y-t1.x*t3.y-t2.x*t1.y;
}
inline bool cmp(const usu &t1,const usu &t2)
{
return det({p[1].x,p[1].y},t1,t2)<0;
}
void read()
{
f>>n;
for(int i=1;i<=n;++i)
{
f>>p[i].x>>p[i].y;
if(p[i]<p[mipoz]) mipoz=i;
}
}
int main()
{
read();
swap(p[1],p[mipoz]);
sort(p+2,p+n+1,cmp);
st[++vf]=1;
for(int i=2;i<=n;++i)
{
while(vf>1&&det(p[st[vf-1]],p[st[vf]],p[i])>0) --vf;
st[++vf]=i;
}
g<<vf<<'\n';
while(vf)
{
g<<setprecision(6)<<fixed<<p[st[vf]].x<<' '<<p[st[vf]].y<<'\n';
--vf;
}
return 0;
}