Pagini recente » Cod sursa (job #1884850) | Cod sursa (job #848259) | Cod sursa (job #1740514) | Cod sursa (job #1755101) | Cod sursa (job #799068)
Cod sursa(job #799068)
#include <cstdio>
#include <stack>
#include <algorithm>
#define N 120005
#define oo 1000000005
using namespace std;
struct punct
{
double X,Y;
}puncte[N],minPct,sol[N];
int elem;
int n;
void citire()
{
minPct.X = oo;
minPct.Y = oo;
int poz;
scanf("%d",&n);
for(int i =0 ; i < n; i++)
{
scanf("%lf %lf",&puncte[i].X,&puncte[i].Y);
if(puncte[i].X < minPct.X || puncte[i].X == minPct.X && puncte[i].Y < minPct.Y)
{
minPct = puncte[i];
poz = i;
}
}
puncte[poz] = puncte[n-1];
n--;
}
double panta(punct p1,punct p2)
{
if(p1.X != p2.X)
return ( (p2.Y - p1.Y) / (p2.X - p1.X) );
return oo;
}
struct cmp{
bool operator()(punct p1, punct p2)
{
return panta(minPct,p1) < panta(minPct,p2);
}
};
double sortPanta()
{
sort(puncte,puncte+n,cmp());
}
/*
x1 y1 1
x2 y2 1
x3 y3 1
*/
double getDeterminate(punct p1, punct p2, punct p3)
{
return ( (p1.X*p2.Y + p2.X*p3.Y + p1.Y*p3.X) - (p3.X * p2.Y + p2.X * p1.Y + p3.Y * p1.X) ) ;
}
void solve()
{
elem = 0;
sol[elem++] = minPct;
sol[elem++] = puncte[0];
for(int i = 1 ; i < n ; i++)
{
if(getDeterminate(sol[elem-2],sol[elem-1],puncte[i]) >= 0)
sol[elem++] = puncte[i];
else
{
while(getDeterminate(sol[elem-2],sol[elem-1],puncte[i]) < 0)
sol[--elem] = puncte[i];
elem++;
}
}
}
void write()
{
printf("%d\n",elem);
for(int i = 0; i < elem ; i ++)
{
printf("%lf %lf\n",sol[i].X,sol[i].Y);
}
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
citire();
sortPanta();
solve();
write();
return 0;
}