Pagini recente » Cod sursa (job #1351779) | Cod sursa (job #2499562) | Cod sursa (job #1990160) | Cod sursa (job #484059) | Cod sursa (job #2527820)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct punct
{
int ord;
double x,y;
} v[120001];
stack<punct> st;
bool compara(punct vs,punct vd)
{
if(vd.y==vs.y) return vs.x<vd.x;
return vs.y<vd.y;
}
double calc_det(punct a,punct b,punct c)
{
return a.x*b.y+b.x*c.y+c.x*a.y-c.x*b.y-b.x*a.y-a.x*c.y;
}
int main()
{
int n;
fin>>n;
for(int i=1; i<=n; i++)
{
fin>>v[i].x>>v[i].y;
}
sort(v+1,v+1+n,compara);
for(int i=1; i<=n; i++)
{
v[i].ord=i;
}
int t[120001]= {0};
punct vf,baz;
vf=v[n];
baz=v[1];
t[1]=1;
st.push(baz);
st.push(v[2]);
t[2]=1;
for(int i=3; i<=n-1; i++)
{
punct b=st.top();
st.pop();
punct a=st.top();
punct c=v[i];
if(calc_det(a,b,c)<=0)
{
st.push(b);
st.push(c);
t[c.ord]=1;
}
else
{
t[b.ord]=0;
bool ok=true;
while(ok==true and st.size()>1)
{
b=a;
st.pop();
a=st.top();
if(calc_det(a,b,c)<=0)
{
st.push(b);
ok=false;
}
else
{
t[b.ord]=0;
}
}
st.push(c);
t[c.ord]=1;
}
}
punct b=st.top();
st.pop();
punct a=st.top();
if(calc_det(a,b,v[n])<=0)
{
st.push(b);
st.push(v[n]);
t[n]=1;
}
else
{
bool ok=true;
while(ok==true and st.size()>1)
{
t[b.ord]=0;
b=a;
st.pop();
a=st.top();
if(calc_det(a,b,v[n])<=0)
{
st.push(b);
ok=false;
}
}
st.push(v[n]);
t[n]=1;
}
int j=-1;
for(int i=n; i>1; i--)
{
if(t[i]==0)
{
j=i;
break;
}
}
if(j!=-1)
{
int siz=st.size();
st.push(v[j]);
t[j]=1;
for(int i=j-1; i>1; i--)
{
if(t[i]==0)
{
punct b=st.top();
st.pop();
punct a=st.top();
punct c=v[i];
if(calc_det(a,b,c)<=0)
{
st.push(b);
st.push(c);
t[c.ord]=1;
}
else
{
t[b.ord]=0;
bool ok=true;
while(ok==true and st.size()>1)
{
b=a;
st.pop();
a=st.top();
if(calc_det(a,b,c)<=0)
{
st.push(b);
ok=false;
}
else
{
t[b.ord]=0;
}
}
st.push(c);
t[c.ord]=1;
}
}
}
punct b=st.top();
st.pop();
punct a=st.top();
if(calc_det(a,b,v[1])<=0)
{
st.push(b);
}
else
{
bool ok=true;
while(ok==true and st.size()>1)
{
t[b.ord]=0;
b=a;
st.pop();
a=st.top();
if(calc_det(a,b,v[1])<=0)
{
st.push(b);
ok=false;
}
}
}
}
fout<<st.size()<<endl;
fout<< fixed<<setprecision(12)<<v[1].x<<' ';
fout<< fixed<<setprecision(12)<<v[1].y<<endl;
while(st.size()>1)
{
punct x1=st.top();
st.pop();
fout<< fixed<<setprecision(12)<<x1.x<< ' ';
fout<< fixed<<setprecision(12)<<x1.y<<endl;
}
return 0;
}