Pagini recente » Cod sursa (job #1138008) | Cod sursa (job #2015291) | Cod sursa (job #271858) | Statistici Matei Resmerita (Fulger99999) | Cod sursa (job #1098090)
#include <fstream>
#include <algorithm>
#include <cmath>
#include <utility>
#define NMAX 120005
#define x first
#define y second
#define mp(x,y) make_pair(x,y)
using namespace std;
FILE* f=freopen("infasuratoare.in","r",stdin);
FILE* o=freopen("infasuratoare.out","w",stdout);
typedef pair<double,double> Point;
Point pts[NMAX],start;
int n;
int stk[NMAX],top=1;
double crossprod(Point a, Point b, Point c)
{
return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
bool compare(Point a, Point b)
{
return crossprod(pts[0],a,b)<0;
}
int main()
{
scanf("%d",&n);
start=mp(9999999999.0,9999999999.0);
int pos;
for(int i=0;i<n;++i)
{
double x,y;
scanf("%lf%lf",&x,&y);
pts[i]=mp(x,y);
if(pts[i]<start)
start=pts[i],pos=i;
}
swap(pts[0],pts[pos]);
sort(pts+1,pts+n,compare);
for(int i=1;i<n;++i)
{
while(top-2>=0&&crossprod(pts[stk[top-2]],pts[stk[top-1]],pts[i])>0)
top-=1;
stk[top++]=i;
}
printf("%d\n",top);
for(int i=top-1;i>=0;--i)
printf("%.6lf %.6lf\n",pts[stk[i]].x,pts[stk[i]].y);
return 0;
}