# Cod sursa(job #2019707)

Utilizator Data 8 septembrie 2017 12:58:52 Infasuratoare convexa 100 cpp done Arhiva educationala 1.92 kb
``````#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>

using namespace std;

const double eps=1.0e-14;

struct Point
{
double x,y;
};

vector<Point>P;
vector<int>h;

Point LL;

double dist(Point P1,Point P2)
{
return sqrt((P1.x-P2.x)*(P1.x-P2.x)+(P1.y-P2.y)*(P1.y-P2.y));
}

double cp (Point P1,Point P2,Point P3)
{
return (P2.x-P1.x)*(P3.y-P2.y)-(P2.y-P1.y)*(P3.x-P2.x);
}

int ccw(Point P1,Point P2,Point P3)
{
double c;
c=cp(P1,P2,P3);
if (fabs(c)<eps)
return 0;
if (c>=eps)
return 1;
return -1;
}

bool cmp(Point P1,Point P2)
{
int c=ccw(LL,P1,P2);
if (c==1)
return 1;
if (c==-1)
return 0;
double d1,d2;
d1=dist(LL,P1);
d2=dist(LL,P2);
if (d1-d2<eps)
return 1;
return 0;
}

int main()
{
int n,i,i2=-1,top;
Point p,p1;
p1.x=1000000001,p1.y=1000000001;
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
for (i=0; i<n; i++)
{
scanf("%lf%lf",&p.x,&p.y);
if (p1.y-p.y>=eps)
{
p1.x=p.x;
p1.y=p.y;
i2=i;
}
else if (fabs(p1.y-p.y)<eps)
if (p1.x-p.x>=eps)
{
p1.x=p.x;
p1.y=p.y;
i2=i;
}
P.push_back(p);
}
LL=P[i2];
swap(P[0],P[i2]);
sort(P.begin()+1,P.end(),cmp);
P.push_back(P[0]);
h.push_back(0);
h.push_back(1);
i=2;
top=1;
while (i<=n)
{
top=h.size()-1;
if (ccw(P[h[top-1]],P[h.back()],P[i])>0)
{
h.push_back(i);
i++;
}
else
h.pop_back();
}
printf("%d\n",top+1);
for (i=0;i<=top;i++)
printf("%lf %lf\n",P[h[i]].x,P[h[i]].y);
return 0;
}
``````