Pagini recente » Cod sursa (job #390951) | Cod sursa (job #2615768) | Cod sursa (job #917554) | Cod sursa (job #495417) | Cod sursa (job #2662942)
#include <bits/stdc++.h>
using namespace std;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
typedef long double ld;
typedef pair<ld,ld> pdd;
const int lim=12e4+5;
#define x first
#define y second
pdd p[lim];
bool mycmp(pdd a,pdd b)
{
return (a.y-p[1].y)*(b.x-p[1].x)<(b.y-p[1].y)*(a.x-p[1].x);
}
bool ok(pdd a,pdd b,pdd c)
{
return (b.y-a.y)*(c.x-b.x)<(c.y-b.y)*(b.x-a.x);
}
vector<pdd> st;
int main()
{
int n;
in>>n;
for(int i=1;i<=n;++i)
in>>p[i].x>>p[i].y;
for(int i=2;i<=n;++i)
if(p[i].y<p[1].y or (p[i].y==p[1].y and p[i].x<p[1].x))
swap(p[1],p[i]);
sort(p+2,p+n+1,mycmp);
st.push_back(p[1]);
pdd last;
for(int i=2;i<=n;++i)
{
while(st.size()>=3)
{
last=st.back(); st.pop_back();
if(ok(st.back(),last,p[i]))
{
st.push_back(last);
break;
}
}
st.push_back(p[i]);
}
out<<st.size()<<'\n';
for(pdd a:st)
out<<fixed<<setprecision(8)<<a.x<<' '<<a.y<<'\n';
return 0;
}