Pagini recente » Cod sursa (job #2446732) | Cod sursa (job #337864) | Cod sursa (job #1815126) | Cod sursa (job #1488171) | Cod sursa (job #406189)
Cod sursa(job #406189)
#include<fstream>
#include<stack>
#include<math.h>
#define dmax 120005
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
long long n,p0,crt;
long double ymin,xmin,q,nr,pi=3.141592;
struct punct
{ long double x;
long double y;
long double up;
} p[dmax];
stack<long long>st;
typedef int (*compfn)(const void *,const void *);
int sf(struct punct *a,struct punct *b)
{ if(a->up > b->up)
return 1;
else if(a->up < b->up)
return -1;
return 0;
}
long double unghi(long long p2,long long p1)
{ return atan( ( p[p2].y-p[p1].y)/(p[p2].x-p[p1].x)) ;
}
long double prod_i(long long a,long long b,long long c)
{ long double p1,p2;
p1=(p[a].x - p[c].x)*(p[b].y - p[c].y);
p2=(p[b].x - p[c].x)*(p[a].y - p[c].y);
return ( p1 - p2 );
}
int main()
{ long long i;
in>>n;
for(i=0;i<n;i++)
in>>p[i].x>>p[i].y;
in.close();
ymin=-1000000000;
xmin=-1000000000;
for(i=0;i<n;i++)
{ if(p[i].y < ymin || ymin==-1000000000)
{ ymin=p[i].y;
xmin=p[i].x;
p0=i;
}
if(p[i].y==ymin)
if(p[i].x<xmin)
p0=i;
}
for(i=0;i<n;i++)
if(i!=p0)
{ p[i].up=unghi(i,p0);
if(p[i].up <=0) p[i].up=pi+p[i].up;
}
qsort((void*)&p,n,sizeof(struct punct),(compfn)sf);
st.push(0);
st.push(1);
st.push(2);
for(i=3;i<n;i++)
{ while(prod_i (i, st.top(), *(&st.top()-1) ) >=0 )
st.pop();
st.push(i);
}
out<<st.size()<<'\n';
for(i=st.size()-1;i>=0;i--)
{ crt=*(&st.top()-i);
out<<fixed<<p[crt].x<<" "<<p[crt].y<<'\n';
}
out.close();
return 0;
}