Pagini recente » Cod sursa (job #982519) | Cod sursa (job #1785274) | Cod sursa (job #1836155) | Cod sursa (job #1040208) | Cod sursa (job #2926428)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
long double aria(pair<long double,long double>a1,pair<long double,long double>a2,pair<long double,long double>a3)
{
return a1.first*a2.second+a2.first*a3.second+a3.first*a1.second-a1.second*a2.first-a2.second*a3.first-a3.second*a1.first;
}
long double vir(pair<long double,long double> a1,pair<long double,long double> a2,pair<long double,long double> a3)
{
long double ar=aria(a1,a2,a3);
if(ar<0)
return -1;
if(ar>0)
return 1;
return 0;
}
bool cmp(pair<int,int>x,pair<int,int>y)
{
return x.first*y.second>x.second*y.first;
}
vector <pair<long double,long double>>v,st,st1,rez;
int main()
{
pair<long double,long double>pt;
long double n;
fin>>n;
for(long double i=1; i<=n; i++)
{
fin>>pt.first>>pt.second;
v.push_back(pt);
}
sort(v.begin(),v.end());
for(auto it:v)
{
if(st.size()<2)
st.push_back(it);
else
{
long double nr=st.size();
pair<long double,long double> a1,a2,a3;
a2=st[nr-1];
a1=st[nr-2];
a3=it;
while(vir(a1,a2,a3)==-1&&st.size()>1)
{
// fout<<a1.first<<" "<<a2.first<<'\n';
auto it1=st.end();
it1--;
st.erase(it1,st.end());
nr=st.size();
a2=st[nr-1];
a1=st[nr-2];
}
// fout<<st.back().first<<" "<<st.back().second<<" "<<it.first<<" "<<it.second<<'\n';
st.push_back(it);
}
}
for(int i=v.size()-1; i>=0; i--)
{
pair<int,int>it=v[i];
if(st1.size()<2)
st1.push_back(it);
else
{
long double nr=st1.size();
pair<long double,long double> a1,a2,a3;
a2=st1[nr-1];
a1=st1[nr-2];
a3=it;
while(vir(a1,a2,a3)==-1&&st1.size()>1)
{
auto it1=st1.end();
it1--;
st1.erase(it1,st1.end());
nr=st1.size();
a2=st1[nr-1];
a1=st1[nr-2];
}
st1.push_back(it);
}
}
for(auto it:st)
rez.push_back(it);
for(int i=1; i<st1.size()-1; i++)
rez.push_back(st1[i]);
sort(rez.begin(),rez.end(),cmp);
fout<<rez.size()<<'\n';
for(auto it:rez)
{
fout<<fixed<<setprecision(12)<<it.first;
fout<<" ";
fout<<fixed<<setprecision(12)<<it.second;
fout<<'\n';
}
return 0;
}