Pagini recente » Cod sursa (job #568072) | Cod sursa (job #1035650) | Cod sursa (job #2144591) | Cod sursa (job #2425363) | Cod sursa (job #1006414)
#include<fstream>
#include<algorithm>
#include<iomanip>
#define MAX 120100
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int i,n,s[MAX],k;
bool viz[MAX];
struct vct
{
double x,y;
}v[MAX];
long double cmp(vct A,vct B)
{
if(A.x!=B.x)
return A.x>B.x;
else
return A.y<B.y;
}
long double verf(int i,int j,int k)
{
double vff;
vff=v[i].x*v[j].y+v[j].x*v[k].y+v[i].y*v[k].x-v[i].y*v[j].x-v[j].y*v[k].x-v[i].x*v[k].y;
return vff;
}
int main ()
{
f>>n;
for(i=1;i<=n;++i)
f>>v[i].x>>v[i].y;
sort(v+1,v+n+1,cmp);
viz[2]=1;
s[1]=1;
s[2]=2;
k=2;
for(i=3;i<=n;++i)
{
if(verf(s[k-1],s[k],i)<0)
{
s[++k]=i;
viz[i]=1;
}
else
{
while(verf(s[k-1],s[k],i)>=0 && k>1)
{
viz[s[k]]=0;
s[k]=0;
k--;
}
s[++k]=i;
viz[i]=1;
}
}
for(i=n-1;i>=1;--i)
{
if(!viz[i])
{
if(verf(s[k-1],s[k],i)<0)
{
s[++k]=i;
viz[i]=1;
}
else
{
while(verf(s[k-1],s[k],i)>=0 && k>1)
{
viz[s[k]]=0;
s[k]=0;
k--;
}
s[++k]=i;
viz[i]=1;
}
}
}
g<<k-1<<"\n";
k--;
for(i=k-1;i>=1;--i)
g<<fixed<<setprecision(6)<<v[s[i]].x<<" "<<v[s[i]].y<<"\n";
g<<v[s[k]].x<<" "<<v[s[k]].y<<"\n";
f.close();
g.close();
return 0;
}