Pagini recente » Cod sursa (job #702511) | Cod sursa (job #1655759) | Cod sursa (job #422726) | Cod sursa (job #2065320) | Cod sursa (job #393651)
Cod sursa(job #393651)
#include<stdio.h>
#include<math.h>
#include<algorithm>
using namespace std;
#define nmax 120050
#define inf 1<<30
#define Constanta 7
struct cetate
{
double x,y,p;
} v[nmax];
int n,m=0,st[nmax],vf;
double dx,dy;
int cmp(cetate i,cetate j)
{
return (i.p < j.p);
}
double dist(cetate,cetate);
void init();
void cit();
void solve();
void swap(int,int);
double det(cetate i,cetate j,cetate k)
{
return (i.x*j.y + j.x*k.y + k.x*i.y - j.y*k.x - k.y*i.x - i.y*j.x);
}
int main()
{
cit();
init();
solve();
return 0;
}
void init()
{
swap(1,m);
for(int i=2;i<=n;++i)
{
dx=v[i].x-v[1].x;
dy=v[i].y-v[1].y;
if (dx>0)
v[i].p=atan((double)dy/dx);
if (dx==0)
v[i].p=M_PI_2;
if (dx<0)
v[i].p=atan((double)dy/dx) + M_PI;
// printf("(%d,%d) : %.5lf\n",v[i].x,v[i].y,v[i].p);
}
sort(v+2,v+n+1,cmp);
}
void solve()
{
st[++vf]=1;
for(int i=2;i<=n;++i)
{
st[++vf]=i;
for ( ; vf>2 && det( v[st[vf-2]] , v[st[vf-1]] , v[st[vf]] ) <= 0 ; )
st[--vf]=i;
}
printf("%d\n",vf);
for(int j=1;j<=vf;++j)
printf("%.6lf %.6lf\n",v[st[j]].x,v[st[j]].y);
}
void cit()
{
v[0].x=inf; v[0].y=inf;
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[m].y > v[i].y)
m=i;
else
if (v[m].y == v[i].y && v[m].x > v[i].x)
m=i;
}
}
void swap(int i,int j)
{
double aux=v[i].x;
v[i].x=v[j].x;
v[j].x=aux;
aux=v[i].y;
v[i].y=v[j].y;
v[j].y=aux;
}
double dist(cetate i,cetate j)
{
return ((i.x-j.x)*(i.x-j.x) + (i.y-j.y)*(i.y-j.y));
}