Pagini recente » Cod sursa (job #468468) | Cod sursa (job #2501116) | Cod sursa (job #1850304) | Cod sursa (job #2345346) | Cod sursa (job #1131323)
#include<cstdio>
#include<algorithm>
#include<vector>
#define x first
#define y second
#define DIF 1e-12
#define NMAX 120010
using namespace std;
typedef pair<double,double> Punct;
Punct V[NMAX],St[NMAX];
int N,H;
inline bool cmp1(double x,double y)
{
if (x+DIF<y) return true;
if (y+DIF<x) return false;
return true;
}
inline double Det(Punct A,Punct B,Punct C)
{
return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}
inline bool cmp(Punct A,Punct B)
{
return (cmp1(Det(V[1],A,B),1));
}
inline void Sort_Points(int N)
{
Punct Aux;
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);
}
inline void Write_Data()
{
printf("%d\n",H);
printf("%.9lf %.9lf\n",St[1].x,St[1].y);
for (int i=H;i>=2;--i)
printf("%.9lf %.9lf\n",St[i].x,St[i].y);
}
inline void Solve(int N)
{
H=2; St[1]=V[1]; St[2]=V[2];
for (int i=3;i<=N;++i)
{
while ( H>=2 && Det(St[H-1],St[H],V[i])>0) H--;
St[++H]=V[i];
}
}
inline void Load_Data(int &N)
{
double X,Y;
scanf("%d",&N);
for (int i=1;i<=N;++i)
scanf("%lf%lf",&V[i].x,&V[i].y);
}
int main()
{
freopen("infasuratoare.in","r",stdin); freopen("infasuratoare.out","w",stdout);
Load_Data(N);
Sort_Points(N);
Solve(N);
Write_Data();
fclose(stdin); fclose(stdout);
return 0;
}