Pagini recente » Cod sursa (job #2588726) | Cod sursa (job #2457973) | Cod sursa (job #2420304) | Cod sursa (job #512665) | Cod sursa (job #883093)
Cod sursa(job #883093)
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
struct punct
{
double x;
double y;
}v[120100];
punct st[120100];
bool cmp(punct a,punct b)
{
double dx1 = a.x-v[1].x, dx2 = b.x-v[1].x;
double dy1 = a.y-v[1].y, dy2 = b.y-v[1].y;
return dx1*dy2 > dx2*dy1; // varianta: return atan2(dy1,dx1) > atan2(dy2,dx2);}
}
double det(punct a[3])
{
double sum=0.0;
for(int i=0;i<3;i++)
{
sum+=a[i].x*a[(i+1)%3].y;
sum-=a[(i+1)%3].x*a[i].y;
}
return sum;
}
int n;
int poz;
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%lf%lf",&v[i].x,&v[i].y);
if(v[i].x<v[1].x)
swap(v[i],v[1]);
else if(v[i].x==v[1].x&&v[i].y<v[1].y)
swap(v[i],v[1]);
}
sort(v+2,v+n+1,cmp);
poz=2;
st[1]=v[1];
st[2]=v[2];
for(int i=3;i<=n;i++)
{
st[++poz]=v[i];
if(poz>=3)
while(poz>=3&&det(st+poz-2)<=0)
{
st[poz-1]=st[poz];
poz--;
}
}
printf("%d\n",poz);
for(int i=1;i<=poz;i++)
printf("%.6lf %.6lf\n",st[i].x,st[i].y);
return 0;
}