Pagini recente » Cod sursa (job #858034) | Cod sursa (job #2476807) | Istoria paginii runda/simulare_oji_2023_clasele_11_12_15_martiee/clasament | Cod sursa (job #2843625) | Cod sursa (job #2869896)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n,used[120001],nr;
pair <double,double> v[120001];
int st[120001];
bool cmp (pair<double,double> a,pair <double,double> b)
{
if (a.second>b.second)
{
return 0;
}
else if (a.second==b.second)
{
if (a.first>b.first)
return 1;
else return 0;
}
else return 1;
}
double det (pair<double,double> a,pair <double,double> b,pair <double,double> c)
{
return a.first*b.second+b.first*c.second+c.first*a.second-a.second*b.first-a.first*c.second-c.first*b.second;
}
int main()
{
f>>n;
for (int i=1; i<=n; i++)
{
f>>v[i].first>>v[i].second;
}
sort(v+1,v+1+n,cmp);
//st.push_back(make_pair(v[1].first,v[1].second));
//st.push_back(make_pair(v[2].first,v[2].second));
int i=3;
st[1]=1;
st[2]=2;
used[2]=1;
nr=2;
while (i<=n)
{
if (used[i]==0)
{
while (nr>=2 && det(v[st[nr-1]],v[st[nr]],v[i])<=0)
{
used[st[nr]]=0;
nr--;
}
nr++;
st[nr]=i;
used[st[nr]]=1;
}
i++;
}
i--;
while (i>=1)
{
if (used[i]==0)
{
while (nr>=2 && det(v[st[nr-1]],v[st[nr]],v[i])<=0)
{
used[st[nr]]=0;
nr--;
}
nr++;
st[nr]=i;
used[st[nr]]=1;
}
i--;
}
g<<nr-1<<'\n';
// g<<st.size()+sf.size()-2<<'\n';
g<<fixed<<setprecision(6);
for (int j=1; j<nr; j++)
{
g<<v[st[j]].first<<' '<<v[st[j]].second<<'\n';
}
/*for (int j=1; j<sf.size()-1; j++)
{
g<<setprecision(6)<<sf[j].first<<' '<<sf[j].second<<'\n';
}*/
/*while (!st.empty())
{
cout<<st.back().first<<' '<<st.back().second<<'\n';
}*/
// while (!st.empty())
// {
// cout<<st.top().first<<' '<<st.top().second<<'\n';
// st.pop();
// }
//cout<<v[i].first<<' '<<v[i].second<<'\n';
return 0;
}