Pagini recente » Cod sursa (job #2688528) | Cod sursa (job #57857) | Cod sursa (job #2628008) | Cod sursa (job #1789110) | Cod sursa (job #248336)
Cod sursa(job #248336)
#include <stdio.h>
#include <algorithm>
#include <vector>
#define nmax 120005
#define x first
#define y second
using namespace std;
int n, f=1;
int st [nmax], w [nmax];
vector < pair <double, double> > p (nmax);
void scan ()
{
int i;
scanf ("%d", &n);
for (i=1; i <= n; ++i)
{
scanf ("%lf%lf", &p [i].x, &p [i].y);
if ((p [i].y < p [f].y) || (p [i].y == p [f].y && p [i].x < p [f].x))
f=i;
}
w [++w [0]]=f;
for (i=1; i <= n; ++i)
if (i != f)
w [++w [0]]=i;
}
bool cmp (int i, int j)
{
return (p [i].y-p [f].y)*(p [j].x-p [f].x) < (p [j].y-p [f].y)*(p [i].x-p [f].x);
}
double ccw (int i, int j, int k)
{
return (p [k].x-p [i].x)*(p [j].y-p [i].y)-(p [j].x-p [i].x)*(p [k].y-p [i].y);
}
void infasuratoare ()
{
int i;
st [++st [0]]=1;
st [++st [0]]=2;
for (i=2; i <= n; ++i)
{
while (st [0] > 2 && ccw (w [st [st [0]]], w [st [st [0]-1]], w [i]) <= 0)
--st [0];
st [++st [0]]=i;
}
}
void print ()
{
int i;
printf ("%d\n", st [0]);
for (i=1; i <= st [0]; ++i)
printf ("%lf %lf\n", p [w [st [i]]].x, p [w [st [i]]].y);
}
int main ()
{
freopen ("infasuratoare.in", "r", stdin);
freopen ("infasuratoare.out", "w", stdout);
scan ();
sort (w+2, w+n+1, cmp);
infasuratoare ();
print ();
return 0;
}