Pagini recente » Cod sursa (job #2539283) | Cod sursa (job #2715774) | Cod sursa (job #718224) | Cod sursa (job #2905199) | Cod sursa (job #1334478)
#include <cstdio>
#include <algorithm>
using namespace std;
struct infasuratoare
{
double x, y;
};
infasuratoare a[120001];
int q[120001], nr=0;
bool sel[120001];
bool cmp (infasuratoare c, infasuratoare d)
{
if (c.y==d.y) return c.x<d.x;
else return c.y<d.y;
}
int semn (infasuratoare X, infasuratoare Y, infasuratoare Z)
{
double a=X.y-Y.y;
double b=Y.x-X.x;
double c=Y.y*X.x-Y.x*X.y;
if (a*Z.x+b*Z.y+c>=0) return 1;
else return -1;
}
void solve (int n)
{
int i, p=3, t=1; q[1]=1; q[2]=2; sel[2]=true; nr=2;
while (!sel[1])
{
while (sel[p]==true)
{
if (p==n) t=-1;
p+=t;
}
while (nr>=2 && semn(a[q[nr-1]],a[q[nr]],a[p])==-1)
{
sel[q[nr]]=false;
q[nr]=0; nr--;
}
q[++nr]=p;
sel[p]=true;
}
nr--;
}
int main()
{
int n, i;
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
for (i=1; i<=n; i++) scanf("%lf%lf",&a[i].x,&a[i].y);
sort(a+1,a+n+1,cmp);
solve(n); printf("%d\n",nr);
for (i=1; i<=nr; i++) printf("%lf %lf\n",a[q[i]].x,a[q[i]].y);
return 0;
}