Pagini recente » Cod sursa (job #1225023) | Cod sursa (job #9711) | Cod sursa (job #1205708) | Cod sursa (job #68217) | Cod sursa (job #3288694)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct punct
{
double x,y;
bool t;
}pct[120001];
bool sortpct(punct a,punct b)
{
if(a.x<b.x || (a.x==b.x && a.y<b.y))
return 1;
return 0;
}
double Arie(punct a,punct b,punct c)
{
return a.x*b.y+b.x*c.y+c.x*a.y-c.x*b.y-a.x*c.y-b.x*a.y;
}
punct st[120001];
int main()
{
int n,sz=0;
fin>>n;
for(int i=0;i<n;i++)
fin>>pct[i].x>>pct[i].y;
sort(pct,pct+n,sortpct);
for(int i=1;i<n-1;i++)
{
double arie=Arie(pct[0],pct[n-1],pct[i]);
pct[i].t=(arie>0);
}
st[sz++]=pct[0];
for(int i=1;i<n;i++)
{
if(pct[i].t)
continue;
if(sz==1)
st[sz++]=pct[i];
else
{
while(sz>=2 && Arie(st[sz-2],pct[i],st[sz-1])>0)
sz--;
st[sz++]=pct[i];
}
}
int sz2=sz;
pct[0].t=1;
for(int i=n-1;i>=0;i--)
{
if(!pct[i].t)
continue;
if(sz2==sz)
st[sz2++]=pct[i];
else
{
while(sz2-sz>=1 && Arie(st[sz2-2],pct[i],st[sz2-1])>0)
sz2--;
st[sz2++]=pct[i];
}
}
sz2--;
fout<<fixed<<setprecision(6);
fout<<sz2<<'\n';
for(int i=0;i<sz2;i++)
fout<<st[i].x<<' '<<st[i].y<<'\n';
return 0;
}