Pagini recente » Cod sursa (job #2392731) | Cod sursa (job #1323150) | Cod sursa (job #1005422) | Cod sursa (job #2961385) | Cod sursa (job #2019695)
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
const double eps=10e-12;
struct POINT
{
double x,y;
};
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;
}
POINT ll;
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;
if(d1-d2>=eps)
return 0;
}
vector <POINT> P;
vector <int> h;
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
int n,i,id,top;
double px,py;
POINT now;
scanf("%d",&n);
now.x=now.y=0;
P.push_back(now);
for(i=1;i<=n;++i)
{
scanf("%lf%lf",&px,&py);
now.x=px;
now.y=py;
if((i==1) || ((ll.y==py && ll.x>px) || (ll.y>py)))
{
ll.x=px;
ll.y=py;
id=i;
}
P.push_back(now);
}
P.erase(P.begin()+id);
P[0]=ll;
sort(P.begin()+1,P.end(),cmp);
P.push_back(ll);
h.push_back(0);
h.push_back(1);
i=2;
while(i<=n)
{
if(ccw(P[h[h.size()-2]],P[h[h.size()-1]],P[i])>0)
{
h.push_back(i);
i++;
}
else
h.pop_back();
}
printf("%d\n",h.size()-1);
for(i=0;i<=h.size()-2;++i)
{
now=P[h[i]];
printf("%f %f\n",now.x,now.y);
}
return 0;
}