Pagini recente » Cod sursa (job #3126803) | Cod sursa (job #857466) | Cod sursa (job #618154) | Cod sursa (job #32955) | Cod sursa (job #930820)
Cod sursa(job #930820)
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=120100;
struct pt
{
double x,y;
}x[N],h[N];
int k,n;
bool cmp(pt x1, pt x2)
{
if(x1.x<x2.x)
return true;
if(x1.x==x2.x)
if(x1.y<x2.y)
return true;
return false;
}
void citire()
{
freopen("infasuratoare.in","r",stdin);
scanf("%d",&n);
for(int i=1;i<=n;++i)
scanf("%lf%lf",&x[i].x,&x[i].y);
fclose(stdin);
}
inline double ccw(pt x1, pt x2, pt x3)
{
return (x2.x-x1.x)*(x3.y-x1.y) - (x2.y-x1.y)*(x3.x-x1.x);
}
void hull()
{
for(int i=1;i<=n;++i)
{
while(k>=2&&ccw(h[k-2],h[k-1],x[i])<=0) --k;
h[k++]=x[i];
}
for(int i=n-1,t=k+1;i>=0;--i)
{
while(k>=t&&ccw(h[k-2],h[k-1],x[i])<=0) k--;
h[k++]=x[i];
}
k--;
}
void afisare()
{
freopen("infasuratoare.out","w",stdout);
printf("%d\n",k);
for(int i=0;i<k;++i)
printf("%lf %lf\n",h[i].x,h[i].y);
fclose(stdout);
}
int main()
{
citire();
sort(x+1,x+n+1,cmp);
hull();
afisare();
return 0;
}