Pagini recente » Cod sursa (job #796574) | Cod sursa (job #1728229) | Cod sursa (job #616554) | Cod sursa (job #1749132) | Cod sursa (job #291166)
Cod sursa(job #291166)
#include<stdio.h>
#include<algorithm>
using namespace std;
struct punct {double x,y;}v[120010];
long int i,j,n,k,l,p=1,sol[120010];
int sign (long int i,long int j,long int k)
{
double x,y;
x=(v[i].x-v[k].x)*(v[j].y-v[k].y);
y=(v[j].x-v[k].x)*(v[i].y-v[k].y);
return (x-y>0);
}
struct cmp
{
bool operator()(const punct &a,const punct &b)const
{return (double)(a.x-v[1].x)*(b.y-v[1].y)>(double)(b.x-v[1].x)*(a.y-v[1].y);
}
};
int main(){
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%ld",&n);
for(i=1;i<=n;i++)
{scanf("%lf %lf",&v[i].x,&v[i].y);
if(v[i].x<v[p].x)p=i;
else
if(v[i].x==v[p].x&&v[i].y<v[p].y)p=i;
}
punct aux;
aux=v[p];
v[p]=v[1];
v[1]=aux;
sort(v+2,v+n+1,cmp());
k=1;
sol[1]=1;
for(i=2;i<=n;i++)
{while(k>=2&&sign(sol[k-1],sol[k],i)<1)k--;
k++;
sol[k]=i;
}
printf("%ld\n",k);
for(i=1;i<=k;i++)
printf("%0.4lf %0.4lf\n",v[sol[i]].x,v[sol[i]].y);
return 0;}