Pagini recente » Cod sursa (job #2522164) | Cod sursa (job #1003850) | Cod sursa (job #2609857) | Cod sursa (job #1981077) | Cod sursa (job #719453)
Cod sursa(job #719453)
#include<fstream>
#include<algorithm>
using namespace std;
int i,n,d,st[120024];
struct point
{
double x,y;
}p[120024];
double 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)
{
double 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("%lf %lf",&p[1].x,&p[1].y);
for(i=2;i<=n;++i)
{
scanf("%lf %lf",&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("%lf %lf\n",p[st[i]].x,p[st[i]].y);
fclose(stdin);
fclose(stdout);
return 0;
}