Pagini recente » Cod sursa (job #1730011) | Cod sursa (job #1795806) | Cod sursa (job #1939598) | Cod sursa (job #1253861) | Cod sursa (job #3149723)
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
const int NMAX=120005;
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
typedef long double ld;
typedef pair<ld, ld> pii;
ld det(pii, pii, pii);
vector <pii> convex_hull(pii [], int);
bool cmp(pii, pii);
pii v[NMAX], st[NMAX];
vector <pii> ans;
int n;
int main()
{
int i;
fin>>n;
for(i=1; i<=n; i++) fin>>v[i].first>>v[i].second;
ans=convex_hull(v, n);
fout<<ans.size()<<'\n';
for(auto i:ans) fout<<fixed<<setprecision(10)<<i.first<<' '<<i.second<<'\n';
return 0;
}
vector <pii> convex_hull(pii v[], int n)
{
int i, poz=0, cnt=0;
pii pct={1e9, 1e9};
for(i=1; i<=n; i++)
{
if(v[i].second<pct.second)
{
pct=v[i];
poz=i;
}
else if(v[i].second==pct.second && v[i].first<pct.first)
{
pct=v[i];
poz=i;
}
}
swap(v[1], v[poz]);
sort(v+2, v+n+1, cmp);
st[++cnt]=v[1];
st[++cnt]=v[2];
for(i=3; i<=n; i++)
{
while(cnt>1 && det(v[i], st[cnt-1], st[cnt])>0) cnt--;
st[++cnt]=v[i];
}
vector <pii> ans;
ans.clear();
for(i=cnt; i>=1; i--) ans.push_back(st[i]);
return ans;
}
bool cmp(pii a, pii b)
{
return det(b, v[1], a)<0;
}
ld det(pii a, pii b, pii c)
{
return b.first*c.second-b.second*c.first+a.first*(b.second-c.second)-a.second*(b.first-c.first);
}