Pagini recente » Cod sursa (job #1410007) | Cod sursa (job #639892) | Cod sursa (job #2086455) | Cod sursa (job #1308159) | Cod sursa (job #2044411)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int nmax =120003;
struct Punct
{
double x,y;
};
int n;
Punct a[nmax];
int st[nmax],top,v[nmax];
double F(int i,int j , int p)
{ // determina semiplanul in care se afla p fata de dreapta i,j
return a[p].x*( a[i].y-a[j].y )+a[p].y*(a[j].x-a[i].x)+a[i].x*a[j].y-a[j].x*a[i].y;
}
void Citire()
{
int i;
fin>>n;
for(i=1;i<=n;++i)
fin>>a[i].x>>a[i].y;
}
inline bool cmp(Punct A,Punct B)
{
if(A.y==B.y)
return A.x<B.x;
return A.y<B.y;
}
void Hill() //alg lui Hill
{
sort(a+1,a+n+1,cmp);
st[++top]=1; v[2]=1;
st[++top]=2;
int i;
for(i=3;i<=n;++i)
{
while( top>1 && F(st[top-1],st[top],i) <0)
{ v[st[top]]=0;
top--;
}
st[++top]=i;
v[i]=1;
}
for(i=n-1;i>=1;--i)
if(v[i]==0)
{
while( top>1 && F(st[top-1],st[top],i) <0)
{ v[st[top]]=0;
top--;
}
st[++top]=i;
v[i]=1;
}
}
void Afisare()
{
int i;
fout<<top-1<<"\n";
for(i=1;i<top;++i)
fout<<setprecision(12)<<fixed<<a[st[i]].x<<" "<<a[st[i]].y<<"\n";
}
int main()
{
Citire();
Hill();
Afisare();
return 0;
}