Pagini recente » Cod sursa (job #829065) | Cod sursa (job #813316) | Cod sursa (job #93993) | Cod sursa (job #1560663) | Cod sursa (job #1334692)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int v[120001];
struct punct_t
{
double x,y;
}minp,punct[120001],rasp[120001];
bool det(punct_t a, punct_t b, punct_t c)
{
if((a.x*b.y+b.x*c.y+c.x*a.y)-(a.y*b.x+b.y*c.x+c.y*a.x)>0)
return true;
else
return false;
}
bool comp(punct_t a,punct_t b)
{
if(det(minp,a,b)) return false;
else return true;
}
int main()
{
int n,i,j,k=2,poz=0;
double x,y;
minp.x=1000000001;
minp.y=1000000001;
f>>n;
for(i=1;i<=n;i++)
{
f>>x>>y;
if(x<minp.x||(x==minp.x && y<minp.y))
{
minp.x=x;
minp.y=y;
poz=i;
}
punct[i].x=x;
punct[i].y=y;
}
swap(punct[poz].x,punct[n].x);
swap(punct[poz].y,punct[n].y);
n--;
sort(punct+1,punct+n+1,comp);
rasp[1]=minp;
rasp[2]=punct[1];
for(i=2;i<=n;i++)
{
while(det(rasp[k-1],rasp[k],punct[i]))
{
k--;
}
rasp[++k].x=punct[i].x;
rasp[k].y=punct[i].y;
}
g<<k<<endl;
g<<fixed<<setprecision(6)<<rasp[1].x<<' '<<rasp[1].y<<endl;
for(i=k;i>1;i--)
g<<fixed<<setprecision(6)<<rasp[i].x<<' '<<rasp[i].y<<endl;
return 0;
}