Pagini recente » Cod sursa (job #2248260) | Cod sursa (job #899669) | Cod sursa (job #2547189) | Cod sursa (job #2393704) | Cod sursa (job #2543008)
#include <bits/stdc++.h>
#define ld long double
#define pdd pair<ld, ld>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int n;
ld x, y, m;
vector<pdd>v;
vector<pdd> s;
pdd p1, p2, st;
ld det(pdd p1, pdd p2, pdd p3)
{
ld x1 = p1.first, x2 = p2.first, x3 = p3.first;
ld y1 = p1.second, y2 = p2.second, y3 = p3.second;
return(x1*y2+y1*x3+x2*y3-y2*x3-y1*x2-y3*x1);
}
void alg(int from)
{
for(int i=from; i<n; i++)
{
if(v[i]==st)
continue;
while(det(p1, p2, v[i])>0)
{
s.pop_back();
p2 = p1;
p1 = s[s.size()-2];
}
p1 = p2;
p2 = v[i];
s.push_back(v[i]);
}
}
bool cmp(pdd p1, pdd p2)
{
if(st.first-p1.first==0)
return true;
if(st.first-p2.first==0)
return false;
if((st.second-p1.second)/(st.first-p1.first) > (st.second-p2.second)/(st.first-p2.first ))
return true;
return false;
}
int main()
{
fin>>n;
st.first = 1000000009;
st.second = 1000000009;
for(int i=1; i<=n; i++)
{
fin>>x>>y;
v.push_back(make_pair(x, y));
if(x<st.first)
{
st.first = x;
st.second = y;
}
else if(x==st.first&&y<st.second)
st.second = y;
}
sort(v.begin(), v.end(), cmp);
s.push_back(st);
p1 = st;
if(v[0]!=st)
{
s.push_back(v[0]);
p2 = v[0];
alg(1);
}
else
{
s.push_back(v[1]);
p2 = v[1];
alg(2);
}
fout<<s.size()<<'\n';
reverse(s.begin(), s.end());
for(auto i:s)
fout<<setprecision(13)<<fixed<<i.first<< ' '<<i.second<<'\n';
return 0;
}