Pagini recente » Cod sursa (job #2284212) | Cod sursa (job #2350481) | Cod sursa (job #1870534) | Cod sursa (job #1207975) | Cod sursa (job #903336)
Cod sursa(job #903336)
#include<cstdio>
#include<vector>
#include<algorithm>
#define ER 1e-12
using namespace std;
struct point
{
double x,y;
};
int cmp(double a,double b)
{
if(a+ER<b)return -1;
if(b+ER<a)return 1;
return 0;
}
int Pcmp(point p1,point p2)
{
int r=cmp(p1.x,p2.x);
if(r==0)return cmp(p1.y,p2.y)==-1;
return r==-1;
}
int sgn(point p1,point p2,point p3)
{
return cmp(p1.x*p2.y+p2.x*p3.y+p3.x*p1.y-p2.y*p3.x-p3.y*p1.x-p1.y*p2.x,0);
}
vector<point> points;
vector<int> Q;
int n,used[120002];
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
for(int i=0;i<n;++i)
{
point p;
scanf("%lf%lf",&p.x,&p.y);
points.push_back(p);
}
sort(points.begin(),points.end(),Pcmp);
Q.push_back(0);Q.push_back(1);
used[1]=1;
int step=1,ind=2;
while(ind!=0)
{
while(used[ind])
{
if(ind==n-1)step=-1;
ind+=step;
}
while(Q.size()>1&&sgn(points[Q[Q.size()-1]],points[Q[Q.size()-2]],points[ind])==-1){used[Q.back()]=0;Q.pop_back();}
Q.push_back(ind);
used[ind]=1;
}
Q.pop_back();
printf("%d\n",Q.size());
for(int i=Q.size()-1;i>=0;--i)printf("%lf %lf\n",points[Q[i]].x,points[Q[i]].y);
return 0;
}