Pagini recente » Cod sursa (job #961658) | Cod sursa (job #1058634) | Cod sursa (job #1944499) | Cod sursa (job #387214) | Cod sursa (job #3247500)
#include <algorithm>
#include <fstream>
#include <iomanip>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
const int MAX=120005;
struct ura
{ double x, y;
} v[MAX];
int s[MAX], vf;
bool cmp(ura a, ura b)
{
if(a.x==b.x)
return a.y<b.y;
return a.x<b.x;
}
bool verif_jos(int a, int b, int c)
{
double ax=v[a].x;
double ay=v[a].y;
double bx=v[b].x;
double by=v[b].y;
double cx=v[c].x;
double cy=v[c].y;
return (ax*by+bx*cy+cx*ay-ay*bx-by*cx-cy*ax)<0;
}
int main()
{
int n;
cin>>n;
for(int i=1; i<=n; i++)
{
cin>>v[i].x>>v[i].y;
}
sort(v+1, v+n+1, cmp);
s[++vf]=1;
for(int i=2; i<=n; i++)
{
if(verif_jos(1, n, i) || i==n)
{
while(vf>1 && verif_jos(s[vf-1], s[vf], i))
{
vf--;
}
s[++vf]=i;
}
}
int vf1=vf;
for(int i=n-1; i>=1; i--)
{
if(!verif_jos(1, n, i) || i==1)
{
while(vf>vf1 && verif_jos(s[vf-1], s[vf], i))
{
vf--;
}
s[++vf]=i;
}
}
cout<<vf-1<<endl;
cout<<fixed<<setprecision(6);
for(int i=2; i<=vf; i++)
{
cout<<v[s[i]].x<<" "<<v[s[i]].y<<endl;
}
return 0;
}