Pagini recente » Istoria paginii runda/rar92 | Cod sursa (job #1099938) | Cod sursa (job #289642) | Cod sursa (job #1578001) | Cod sursa (job #1113789)
#include <cstdio>
#include <cmath>
#include <algorithm>
#define Nmax 120005
#define x first
#define y second
using namespace std;
pair<double,double> M[Nmax],S[Nmax],P;
int vf = 2;
int N;
/**
A.x A.y 1
B.x B.y 1
C.x C.y 1
= A.x * B.y + B.x * C.y + C.x * A.y - C.x*B.y - C.y * A.x - B.x * A.y;
*/
double cross(pair<double,double> A, pair<double,double> B, pair<double,double> C)
{
return A.x * B.y + B.x * C.y + C.x * A.y - C.x * B.y - C.y * A.x - B.x * A.y;
}
class cmp{
public:
bool operator()(const pair<double,double> A, const pair<double,double> B)const
{
return cross(M[1],A,B)<0;
}
};
void convex_hull()
{
S[1] = M[1];
S[2] = M[2];
for(int i = 3; i <= N; ++i)
{
while(vf >= 2 && cross(S[vf-1],S[vf],M[i]) > 0)
--vf;
S[++vf] = M[i];
}
}
void afish()
{
printf("%d\n",vf);
for(int i = vf; i>= 1; --i)
printf("%.6lf %.6lf\n",S[i].x,S[i].y);
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&N);
for(int i = 1; i <= N; ++i){
scanf("%lf%lf",&M[i].first,&M[i].second);
}
int pz = 1;
for(int i = 2; i <= N; ++i)
if(M[i] < M[pz])
pz = i;
swap(M[pz],M[1]);
sort(M+2,M+N+1,cmp());
convex_hull();
afish();
return 0;
}