Pagini recente » Cod sursa (job #510340) | Cod sursa (job #2990632) | Cod sursa (job #2966036) | Cod sursa (job #1603750) | Cod sursa (job #719435)
Cod sursa(job #719435)
#include<fstream>
#include<algorithm>
using namespace std;
int i,n,d,st[120024];
struct point
{
float x,y;
}p[120024];
float isleft(point a,point b,point c)
{
return ((b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y));
}
bool comp(point a,point b)
{
float k=isleft(p[1],a,b);
if(k>0) return 1;
return 0;
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
scanf("%f %f",&p[1].x,&p[1].y);
for(i=2;i<=n;++i)
{
scanf("%f %f",&p[i].x,&p[i].y);
if((p[i].x<p[1].x)||(p[i].x==p[1].x&&p[i].y<p[1].y))
{
point aux=p[1];
p[1]=p[i];
p[i]=aux;
}
}
sort(p+2,p+n+1,comp);
st[++d]=1;
for(i=2;i<=n;++i)
{
while(d>1&& isleft(p[st[d-1]],p[st[d]],p[i])<0) --d;
st[++d]=i;
}
printf("%d\n",d);
for(i=1;i<=d;++i) printf("%f %f\n",p[st[i]].x,p[st[i]].y);
fclose(stdin);
fclose(stdout);
return 0;
}