Pagini recente » Cod sursa (job #1869957) | Cod sursa (job #2124785) | Istoria paginii runda/oni_cl_11-12_zi2 | Cod sursa (job #1608117) | Cod sursa (job #483047)
Cod sursa(job #483047)
#include<fstream>
#include<vector>
#include<algorithm>
#define x first
#define y second
#define NMAX 120005
using namespace std;
vector<long> st;
vector< pair<double,double> > p(NMAX);
pair<double,double> w;
long n;
void cit()
{ifstream fin("infasuratoare.in");
fin>>n;
long i;
for( i=1;i<=n;++i)
fin>>p[i].x>>p[i].y;
long o;
o=1;
for(i=2;i<=n;++i)
if((p[o].y>p[i].y)||(p[o].y==p[i].y&&p[o].x>p[i].x))
o=i;
w=p[o];
--n;
p.erase(p.begin()+o);
p[0]=w;
fin.close();
}
int cmp(pair<double,double> a,pair<double,double> b)
{return (a.y-w.y)*(b.x-w.x)<(a.x-w.x)*(b.y-w.y);}
int sign(long i,long j,long k)
{return ((p[i].x-p[j].x)*(p[j].y-p[k].y)+(p[j].y-p[i].y)*(p[j].x-p[k].x))>0;}
ofstream fout("infasuratoare.out");
void solve()
{sort(p.begin()+1,p.begin()+n+1,cmp);
long i;
st.push_back(0);
st.push_back(1);
for(i=2;i<=n;++i)
{ while(st.size()>1&&!sign(st[st.size()-2],st[st.size()-1],i))
st.pop_back();
st.push_back(i);
}
}
void afis()
{
fout<<st.size()<<'\n';
for(long i=0;i<st.size();++i)
{//fout.precision(6);
fout<<p[st[i]].x<<" "<<p[st[i]].y<<'\n';
}
fout.close();
}
int main()
{cit();
solve();
afis();
return 0;
}