Pagini recente » Cod sursa (job #87781) | Cod sursa (job #545706) | Cod sursa (job #1750616) | Cod sursa (job #69388) | Cod sursa (job #932222)
Cod sursa(job #932222)
#include <cstdio>
#include <algorithm>
#define N 120005
using namespace std;
struct pct {
double x,y;
};
int n, s[N], h;
pct puncte[N];
bool viz[N];
bool cmp(pct x, pct y)
{
if (x.x == y.x)
{
if (x.y < y.y)
return true;
return false;
}
if (x.x < y.x)
return true;
return false;
}
double ecuatia(pct a, pct b, pct c)
{
return a.x*(b.y-c.y) + a.y*(c.x-b.x) + b.x*c.y - b.y*c.x;
}
void afisare()
{
printf("%d\n", h);
for(int i=h-1; i>=0; i--)
printf("%.6lf %.6lf\n", puncte[s[i]].x, puncte[s[i]].y);
}
void citire()
{
freopen("infasuratoare.in","rt",stdin);
freopen("infasuratoare.out","wt",stdout);
scanf("%d", &n);
for (int i=0; i<n; i++)
scanf("%lf %lf", &puncte[i].x, &puncte[i].y);
}
void infasor()
{
s[0]=0, s[1]=1, h=1;
viz[1]=1;
int q=1; /// pas
for (int i=2; !viz[0];)
{
while (viz[i])
{
if (i==n-1)
q=-1;
i+=q;
}
while (h>0 && ecuatia(puncte[s[h-1]], puncte[s[h]], puncte[i])>0)
viz[s[h--]]=0;
s[++h]=i;
viz[i]=1;
}
}
int main ()
{
citire();
sort(puncte, puncte+n, cmp);
infasor();
afisare();
return 0;
}