Pagini recente » Cod sursa (job #2278041) | Cod sursa (job #2105667) | Cod sursa (job #1664095) | Cod sursa (job #1192607) | Cod sursa (job #2137843)
#include <bits/stdc++.h>
#define x first
#define y second
#define punct pair<double,double>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int N_MAX=120010;
punct v[N_MAX];
punct stiva[N_MAX];
int N,varf;
double determin(punct a,punct b,punct c)
{
return (c.y-a.y)*(b.x-a.x)-(b.y-a.y)*(c.x-a.x);
}
int crit(const punct p1,const punct p2)
{
return determin(v[1],p1,p2)<0;
}
void convex()
{
int poz=1;
for(int i=2;i<=N;i++)
{
if(v[i]<v[poz])poz=i;
}
swap(v[1],v[poz]);
sort(v+1,v+N+1,crit);
stiva[1]=v[1];
stiva[2]=v[2];
varf=2;
for(int i=3;i<=N;i++)
{
while(varf>2 && determin(stiva[varf-1],stiva[varf],v[i])<0)
varf--;
stiva[++varf]=v[i];
}
}
int main()
{
fin>>N;
for(int i=1;i<=N;i++)fin>>v[i].x>>v[i].y;
convex();
fout<<varf<<'\n';
for(int i=varf;i>=1;i--)
{
fout<<fixed<<setprecision(6)<<stiva[i].x<<' '<<stiva[i].y<<'\n';
}
return 0;
}