Pagini recente » Cod sursa (job #2448844) | Cod sursa (job #2476570) | Cod sursa (job #646951) | Cod sursa (job #1773479) | Cod sursa (job #1124039)
#include <stdio.h>
#include <iomanip>
#include <algorithm>
#define NMAX 120005
#define x first
#define y second
using namespace std;
typedef pair<double,double> Points;
Points V[NMAX],STACK[NMAX],ST[NMAX];
int N,HEAD=2;
void read()
{
scanf("%d\n",&N);
for (int i=1;i<=N;i++)
scanf("%lf %lf\n",&V[i].x,&V[i].y);
}
double cross_product(Points A,Points B,Points C)
{
return (B.x-A.x)*(C.y-A.y) - (B.y-A.y)*(C.x-A.x);
}
int cmp(Points A,Points B)
{
return cross_product(V[1],A,B)<0;
}
void sort_points()
{
int poz=1;
for (int i=2;i<=N;i++)
if (V[i]<V[poz]) poz=i;
swap(V[1],V[poz]);
sort(V+2,V+N+1,cmp);
}
void convex_hull()
{
sort_points();
ST[1]=V[1];
ST[2]=V[2];
for (int i=3;i<=N;i++)
{
while (HEAD>=2 && cross_product(ST[HEAD-1],ST[HEAD],V[i])>0)
HEAD--;
ST[++HEAD]=V[i];
}
}
void print_result()
{
printf("%d\n",HEAD);
for (int i=HEAD;i>=1;i--)
printf("%lf %lf\n",ST[i].x,ST[i].y);
}
int main()
{
freopen ("infasuratoare.in","r",stdin);
freopen ("infasuratoare.out","w",stdout);
read();
convex_hull();
print_result();
fclose(stdin);
fclose(stdout);
return 0;
}