Pagini recente » Cod sursa (job #1165447) | Cod sursa (job #211898) | Cod sursa (job #1741676) | Cod sursa (job #800025) | Cod sursa (job #1125343)
#include <cstdio>
#include <algorithm>
#include <cmath>
#define inFILE "infasuratoare.in"
#define outFILE "infasuratoare.out"
#define x first
#define y second
#define Nmax 120005
using namespace std;
pair<double,double> pct[Nmax];
pair<double,double> stak[Nmax],P;
int N,vf=2;
double cross_prod(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 -
A.y*B.x - B.y*C.x - C.y*A.x;
}
double dist(pair<double,double> A, pair<double,double> B)
{
return sqrt( (A.x-B.x)*(A.x-B.x) + (A.y-B.y)*(A.y-B.y) );
}
class cmp{
public:
bool operator()(const pair<double,double>A,const pair<double,double>B)const
{
if(pct[1].y - A.y == 0 && pct[1].y - B.y == 0 ||
pct[1].x - A.y == 0 && pct[1].y - B.y == 0)
return (dist(pct[1],A) < dist(pct[1],B));
return cross_prod(pct[1],A,B) < 0;
}
};
void read()
{
scanf("%d",&N);
for(int i = 1; i <= N; ++i)
scanf("%lf%lf",&pct[i].x,&pct[i].y);
int pz = 1;
for(int i = 2; i <= N; ++i)
if(pct[i] < pct[pz])
pz = i;
swap(pct[pz],pct[1]);
}
void make_hull()
{
sort(pct+2,pct+N+1,cmp());
stak[1] = pct[1];
stak[2] = pct[2];
for(int i = 3; i <= N; ++i)
{
while(vf >= 2 && cross_prod(stak[vf-1],stak[vf],pct[i]) > 0)
--vf;
stak[++vf] = pct[i];
}
}
void print()
{
printf("%d\n",vf);
for(int i = vf; i >= 1; --i)
printf("%.6lf %.6lf\n",stak[i].x,stak[i].y);
}
int main()
{
freopen ( inFILE, "r", stdin );
freopen ( outFILE, "w", stdout );
read();
make_hull();
print();
return 0;
}