Pagini recente » Cod sursa (job #638821) | Cod sursa (job #1918164) | Cod sursa (job #2303057) | Cod sursa (job #1628496) | Cod sursa (job #1131227)
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define x first
#define y second
#define mp make_pair
#define pb push_back
#define NMAX 120010
#define DIF 1e-12
using namespace std;
vector < pair<double,double> > V;
int St[NMAX],N;
bool used[NMAX];
inline void Write_Data()
{
printf("%d\n",St[0]);
for (int i=1;i<=St[0];++i)
printf("%.6lf %.6lf\n",V[St[i]].x,V[St[i]].y);
}
inline int cmp(double x,double y)
{
if (x+DIF<y) return 1;
if (y+DIF<x) return -1;
return 0;
}
inline int Sign(int p1,int p2,int p3)
{
double P1,P2,P3,P4,P5,P6,Det;
P1=V[p1].x * V[p2].y; P2=V[p2].x * V[p3].y; P3=V[p3].x * V[p1].y;
P4=-(V[p2].y * V[p3].x); P5=-(V[p1].y * V[p2].x); P6=-(V[p3].y * V[p1].x);
Det=P1+P2+P3+P4+P5+P6;
return cmp(Det,1);
}
inline void Solve(int N)
{
int k=2,pas=1,i=3;
used[2]=true; St[1]=1; St[2]=2;
while (!used[1])
{
while (used[i])
{if (i==N) pas=-1; i+=pas;}
while (k>=2 && Sign(St[k-1],St[k],i)==-1)
used[St[k--]]=false;
used[i]=true; St[++k]=i;
}
St[0]=k;
}
inline void Load_Data(int &N)
{
double X,Y;
scanf("%d",&N);
for (int i=1;i<=N;++i)
scanf("%lf%lf",&X,&Y), V.pb(mp(X,Y));
sort(V.begin(),V.end());
memset(used,false,sizeof(used));
}
int main()
{
freopen("infasuratoare.in","r",stdin); freopen("infasuratoare.out","w",stdout);
Load_Data(N);
Solve(N);
Write_Data();
fclose(stdin); fclose(stdout);
return 0;
}