Pagini recente » Cod sursa (job #2166596) | Cod sursa (job #2581648) | Cod sursa (job #1908348) | Cod sursa (job #2230202) | Cod sursa (job #1086114)
//Infasuratoare convexa
#include <fstream>
#include <math.h>
#include <algorithm>
#define eps 0.00000000001
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct punct
{
double x,y;
}p[120001],s[120001],aux;
int minp=1,vf,n;
/*
inline double dist(punct A, punct B)
{
return sqrt((A.x-B.x)*(A.x-B.x)-(A.y-B.y)*(A.y-B.y));
}
*/
bool comp(punct A, punct B)
{
double u1=(A.y-s[0].y)/(A.x-s[0].x);
double u2=(B.y-s[0].y)/(B.x-s[0].x);
return u1<u2;
}
inline double arie2_s(punct A, punct B, punct C)
{
return A.x*B.y+B.x*C.y+C.x*A.y-C.x*B.y-B.x*A.y-A.x*C.y;
}
int main()
{
double d;
fin>>n;
for (int i=1;i<=n;++i)
fin>>p[i].x>>p[i].y;
for (int i=2;i<=n;++i)
if (p[minp].x>p[i].x) minp=i;
else if (p[minp].x==p[i].x)
if (p[minp].y>p[i].y) minp=i;
s[0]=p[minp];
p[minp]=p[1];
p[1]=s[0];
sort(p+2,p+n+1,comp);
s[1]=p[2];
vf=1;
for (int i=3;i<=n;++i)
{
d=arie2_s(s[vf-1],s[vf],p[i]);
while (fabs(d)<eps || d<0){
--vf;
d=arie2_s(s[vf-1],s[vf],p[i]);
}
s[++vf]=p[i];
}
fout<<vf+1<<'\n';
for (int i=0;i<=vf;++i)
fout<<s[i].x<<" "<<s[i].y<<'\n';
fin.close();
fout.close();
return 0;
}