Pagini recente » Cod sursa (job #1822662) | Cod sursa (job #2624349) | Cod sursa (job #60876) | Cod sursa (job #2213608) | Cod sursa (job #3246734)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("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, ay=v[a].y, bx=v[b].x, by=v[b].y, cx=v[c].x, cy=v[c].y;
return (ax*by+bx*cy+cx*ay-ay*bx-by*cx-cy*ax)<=0;
}
bool verif_jos2(int a, int b, int c)
{
double ax=v[a].x, ay=v[a].y, bx=v[b].x, by=v[b].y, cx=v[c].x, cy=v[c].y;
return (ax*by+bx*cy+cx*ay-ay*bx-by*cx-cy*ax)>=0;
}
int main()
{
int n;
fin>>n;
for(int i=1; i<=n; i++)
{
fin>>v[i].x>>v[i].y;
}
sort(v+1, v+n+1, cmp);
vf++;
s[1]=1;
for(int i=2; i<=n; i++)
{
if(verif_jos(1, n, i))
{
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_jos2(1, n, i))
{
while(vf>vf1 && verif_jos(s[vf-1], s[vf], i))
{
vf--;
}
s[++vf]=i;
}
}
fout<<vf-1<<'\n';
fout<<fixed<<setprecision(6);
for(int i=2; i<=vf; i++)
{
fout<<v[s[i]].x<<" "<<v[s[i]].y<<'\n';
}
//fout<<v[s[1]].x<<" "<<v[s[1]].y<<'\n';
return 0;
}