Pagini recente » Cod sursa (job #950767) | Cod sursa (job #1303303) | Cod sursa (job #81608) | Cod sursa (job #457380) | Cod sursa (job #1375895)
#include <cstdio>
#include <algorithm>
#define x first
#define y second
#define EPS 0.00000001
#define Nmax 120005
using namespace std;
int N,vf,used[Nmax];
pair<double,double> P[Nmax],Stack[Nmax];
void push(pair<double,double> P){
Stack[++vf] = P;
}
void pop(){
Stack[vf--] = make_pair(0,0);
}
double abso(double d){
if(d > 0)
return d;
return -d;
}
int det(pair<double,double> A, pair<double,double> B, pair<double,double> C)
{
double d = (A.x - C.x)*(B.y - C.y) -
(A.y - C.y)*(B.x - C.x);
if(abso(d) < EPS)
return 0;
if(d > 0) return 1;
return -1;
}
void Read()
{
scanf("%d",&N);
for(int i = 1; i <= N; ++i)
scanf("%lf%lf",&P[i].x,&P[i].y);
}
void Hull()
{
pair<double,double> Pmin,Pmax;
sort(P+1,P+N+1);
Pmin = P[1]; Pmax = P[N];
push(Pmin);
for(int i = 2; i <= N; ++i)
if(det(Pmin,Pmax,P[i]) >= 0)
{
used[i] = 1;
while(vf >= 2 && det(Stack[vf-1],Stack[vf],P[i]) > 0) /// cu >= scoate punctele coliniare
pop();
push(P[i]);
}
for(int i = N - 1; i >= 1; --i)
if(!used[i])
{
used[i] = 1;
while(vf >= 2 && det(Stack[vf-1],Stack[vf],P[i]) > 0)
pop();
push(P[i]);
}
}
void Print()
{
printf("%d\n",vf - 1);
pop();
while(vf >= 1){
printf("%lf %lf\n",Stack[vf].x, Stack[vf].y);
pop();
}
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
Read();
Hull();
Print();
return 0;
}