Pagini recente » Istoria paginii utilizator/trandafir_cosmin | Istoria paginii utilizator/chelaru_razvan | Monitorul de evaluare | Cod sursa (job #781617) | Cod sursa (job #1091856)
#include <fstream>
#include <cstdio>
#include <cmath>
#include <cstdio>
#include <algorithm>
#define Precizie 1000000
#define eps 0.0000001
#define Nmax 120099
using namespace std;
ifstream f("infasuratoare.in");
int N,k;
struct point {double x,y;}P[Nmax],st[Nmax],G;
inline void ReadInput(),PrintOutPut();
inline double CrossProduct(const point &A,const point &B,const point &C);
inline bool Equal(const double &x,const double &y),LessThan(const double &x,const double &y);
inline void ConvexHull();
int main()
{
freopen("infasuratoare.out","w",stdout);
ReadInput();
ConvexHull();
PrintOutPut();
return 0;
}
struct cmp
{
bool operator()(const point &A,const point &B)const
{
return atan2(A.y-G.y,A.x-G.x)<atan2(B.y-G.y,B.x -G.x);
};
};
inline void ConvexHull()
{
sort(P+1,P+1+N,cmp());
st[1]=P[1],st[2]=P[2];
k=2;
for(int i=3;i<=N;++i)
{
while(k>=2 && CrossProduct(st[k-1],st[k],P[i])<0)--k;
st[++k]=P[i];
}
}
inline double CrossProduct(const point &A,const point &B,const point &C)
{
return (B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);
};
inline bool Equal(const double &x,const double &y)
{
if(fabs(x-y)<eps)return 1;
else return 0;
}
inline bool LessThan(const double &x,const double &y)
{
if(1LL*Precizie*x<1LL*Precizie*y)return 1;
else return 0;
}
void ReadInput()
{
f>>N;
f>>P[1].x>>P[1].y;
G.x+=P[1].x,G.y+=P[1].y;
for(int i=2;i<=N;++i)
{
f>>P[i].x>>P[i].y;
G.x+=P[i].x,G.y+=P[i].y;
}
G.x=1.0*G.x/N,G.y=1.0*G.y/N;
}
void PrintOutPut()
{
//solutia a fost generata in ordine trigonometrica
printf("%d\n",k);
for(int i=1;i<=k;++i)printf("%0.6f %0.6f\n",st[i].x,st[i].y);
}