Pagini recente » Cod sursa (job #1791504) | Cod sursa (job #99117) | Cod sursa (job #1804585) | Cod sursa (job #1128802) | Cod sursa (job #3140671)
#include <fstream>
#include <bitset>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
struct el
{
long double x,y;
};
el v[120001];
long double d,xa,xb,xc,ya,yb,yc;
int n,i,k,stiva[120003];
bitset <120001> viz;
int cmp (const el &a,const el &b)
{
if (a.x==b.x)
return a.y<b.y;
return a.x<b.x;
}
int f (int k,int i)
{
if (k<2)
return 0;
xa=v[stiva[k-1]].x;
ya=v[stiva[k-1]].y;
xb=v[stiva[k]].x;
yb=v[stiva[k]].y;
xc=v[i].x;
yc=v[i].y;
d=(yc-ya)*(xb-xa)-(yb-ya)*(xc-xa);
if (d<0)
return 1;
else
return 0;
}
int main()
{
fin>>n;
for (i=1; i<=n; i++)
fin>>v[i].x>>v[i].y;
sort (v+1,v+n+1,cmp);
stiva[++k]=1;
for (i=2; i<=n; i++)
{
if (viz[i]==1)
continue;
while (k>2&&f (k,i)==1)
{
viz[stiva[k]]=0;
k--;
}
stiva[++k]=i;
viz[i]=1;
}
for (i=n-1; i>0; i--)
{
if (viz[i]==1)
continue;
while (k>2&&f (k,i)==1)
{
viz[stiva[k]]=0;
k--;
}
stiva[++k]=i;
viz[i]=1;
}
fout<<k-1<<"\n";
for (i=1; i<k; i++)
fout<<fixed<<setprecision (6)<<v[stiva[i]].x<<" "<<v[stiva[i]].y<<"\n";
return 0;
}