Pagini recente » Cod sursa (job #1101991) | Cod sursa (job #1690729) | Cod sursa (job #1195327) | Cod sursa (job #369508) | Cod sursa (job #2528035)
#include <iostream>
#include <fstream>
#include <stack>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct punct
{
float x, y;
int ord;
} v[120001];
bool comp(punct A, punct B)
{
if(A.y==B.y)
return A.x<B.x;
return A.y<B.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-a.y*b.x-c.y*a.x;
}
stack <punct> st;
int t[120001], n;
int main()
{
punct a, b, c;
fin>>n;
for(int i=1; i<=n; i++)
{
fin>>v[i].x>>v[i].y;
}
sort(v+1,v+1+n,comp);
for(int i=1; i<=n; i++)
v[i].ord=i;
st.push(v[1]);
st.push(v[2]);
t[1]=1;
t[2]=1;
for(int i=3; i<=n-1; i++)
{
b=st.top();
st.pop();
a=st.top();
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;
}
}
b=st.top();
st.pop();
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)
{
st.push(v[j]);
t[j]=1;
for(int i=j-1; i>1; i--)
{
if(t[i]==0)
{
b=st.top();
st.pop();
a=st.top();
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;
}
}
}
}
b=st.top();
st.pop();
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<<' '<<v[1].y<<endl;
while(st.size()>1)
{
a=st.top();
fout<<fixed<<setprecision(12)<<a.x<<' '<<a.y<<endl;
st.pop();
}
}