Pagini recente » Cod sursa (job #2564481) | Cod sursa (job #1208818) | Cod sursa (job #1660092) | Cod sursa (job #1747639) | Cod sursa (job #1341278)
#include <cstdio>
#include <algorithm>
#include <iostream>
#define Nmax 120005
#define x first
#define y second
using namespace std;
int N,vf;
pair<double,double> pct[Nmax],S[Nmax];
double det(pair<double,double> A,pair<double,double> B, pair<double,double> C)
{
return (B.x-A.x)*(C.y-A.y) - (B.y-A.y)*(C.x-A.x);
}
class cmp{
public:
bool operator()(const pair<double,double> &A,const pair<double,double> &B) const
{
return (det(pct[1],A,B) < 0);
}
};
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",&pct[i].x,&pct[i].y);
int ind = 1;
for(int i = 2; i <= N; ++i)
if(pct[i] < pct[ind])
ind = i;
swap(pct[1],pct[ind]);
sort(pct+2,pct+N+1,cmp());
S[++vf] = pct[1];
S[++vf] = pct[2];
for(int i = 3; i <= N; ++i)
{
while(vf >= 2 && det(S[vf-1],S[vf],pct[i]) > 0)
--vf;
S[++vf] = pct[i];
}
printf("%d\n",vf);
while(vf)
{
printf("%lf %lf\n",S[vf].x, S[vf].y);
--vf;
}
return 0;
}