Pagini recente » Cod sursa (job #530515) | Cod sursa (job #2530249) | Cod sursa (job #1218341) | Cod sursa (job #462930) | Cod sursa (job #2926691)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
long double r=0;
vector <pair<long double,long double>>v,st,st1,rez;
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 comp(pair<long double,long double>x,pair<long double,long double>y)
{
long double ar=aria(v[0],x,y);
if(ar>0)
return true;
return false;
}
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);
}
for(long double i=1; i<n; i++)
{
if(v[r]>v[i])
r=i;
}
swap(v[0],v[r]);
sort(v.begin()+1,v.end(),comp);
st.push_back(v[0]);
st.push_back(v[1]);
for(auto it:v)
{
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);
}
fout<<st.size()<<'\n';
for(auto it:st)
{
fout<<fixed<<setprecision(12)<<it.first;
fout<<" ";
fout<<fixed<<setprecision(12)<<it.second;
fout<<'\n';
}
return 0;
}