Pagini recente » Istoria paginii runda/blat9/clasament | Istoria paginii utilizator/voinica_mihai_virgil_321cb | Cod sursa (job #394098) | Cod sursa (job #848864) | Cod sursa (job #1598043)
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#define infinity 2000000000
#define eps 1.0e-12
using namespace std;
int n,lli;
double x,y;
struct point
{
double x,y;
};
point v[120005],aux;
vector<point> st;
int ccv(point p1,point p2,point p3)
{
double cp=(p2.x-p1.x)*(p3.y-p2.y)-
(p2.y-p1.y)*(p3.x-p2.x);
if(cp>=eps) return 1;
if(cp<=-eps) return -1;
return 0;
}
int cmp(point a,point b)
{
return ccv(v[1],a,b)>0;
}
int main()
{
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
scanf("%d",&n);
v[0].x=v[0].y=infinity;
for(int i=1;i<=n;i++)
{
scanf("%lf %lf",&x,&y);
v[i].x=x;
v[i].y=y;
if((v[lli].y-v[i].y)>=eps)
lli=i;
else if((fabs(v[lli].y-v[i].y)<eps)&&(v[lli].x-v[i].x)>=eps)
lli=i;
}
aux=v[lli];
v[lli]=v[1];
v[1]=aux;
sort(v+2,v+n+1,cmp);
n++;
v[n]=v[1];
st.push_back(v[1]);
st.push_back(v[2]);
for(int i=3;i<=n;i++)
{
while(ccv(st[st.size()-2],st[st.size()-1],v[i])<1)
st.pop_back();
st.push_back(v[i]);
}
printf("%d\n",st.size()-1);
for(int i=0;i<st.size()-1;i++)
{
printf("%lf %lf\n",st[i].x,st[i].y);
}
return 0;
}