Pagini recente » Cod sursa (job #1165095) | Cod sursa (job #2095208) | Cod sursa (job #1353890) | Cod sursa (job #1942936) | Cod sursa (job #1880929)
#include <fstream>
#include <algorithm>
#include <iomanip>
#define INF 0x3f3f3f3f;
#define NMAX 120005
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct punct
{
double x,y;
}pct[NMAX],mini,st[NMAX];
int N;
double Aria(punct a, punct b, punct c)
{
return (a.x - b.x) * (c.y - b.y) - (a.y - b.y) * (c.x - b.x);
}
int comp(const punct& a, const punct& b)
{
return (Aria(a,mini,b) > 0);
}
int main()
{
int i, poz;
fin >> N;
mini.x = mini.y = INF;
for(i=1; i<=N; i++)
{
fin>>pct[i].x>>pct[i].y;
if(pct[i].x < mini.x)
{
mini = pct[i];
poz = i;
}
else if(pct[i].x == mini.x && pct[i].y < mini.y)
mini = pct[i], poz = i;
}
swap(pct[1],pct[poz]);
sort(pct+2,pct+N+1,comp);
st[1] = mini;
int po = 2;
for(i = po; i<=N;i++)
{
while(po > 2 && Aria(st[po-2], st[po-1], pct[i])>=0)
po--;
st[po] = pct[i];
po++;
}
fout<<po-1<<'\n';
fout<<setprecision(6)<<fixed;
for(i=1; i<po; ++i)
fout<<st[i].x<<" "<<st[i].y<<'\n';
return 0;
}