Pagini recente » Cod sursa (job #164580) | Cod sursa (job #1418096) | Cod sursa (job #367584) | Cod sursa (job #1280166) | Cod sursa (job #2003987)
#include <fstream>
#include <algorithm>
#define NM 120005
#define COR 1000000005
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct punct {double x, y, u;} V[NM], Stiva[NM];
int n, vf;
inline double dir(punct a, punct b, punct c)
{
return (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x);
}
bool comp(punct a, punct b)
{
return dir(V[1], a, b)>0;
}
void citeste()
{
int i, nod;
float minim=COR;
fin>>n;
for(i=1; i<=n; i++)
{
fin>>V[i].x>>V[i].y;
if (V[i].y<minim)
{
minim=V[i].y;
nod=i;
}
}
swap(V[1], V[nod]);
}
void GrahamScan()
{
int i;
Stiva[1]=V[1];
Stiva[2]=V[2];
V[n+1]=V[1];
vf=2;
for (i=3; i<=n+1; i++)
{
while (dir(Stiva[vf-1], Stiva[vf], V[i])<0 && vf>1)
{
vf--;
}
vf++;
Stiva[vf]=V[i];
}
}
int main()
{
int i;
citeste();
sort(V+2, V+n+1, comp);
GrahamScan();
fout<<--vf<<'\n';
for (i=1; i<=vf; i++)
fout<<Stiva[i].x<<" "<<Stiva[i].y<<'\n';
return 0;
}