Pagini recente » Cod sursa (job #2157493) | Cod sursa (job #717577) | Cod sursa (job #2654980) | Cod sursa (job #872688) | Cod sursa (job #1957867)
/// a.cpp
# include <stdio.h>
# include <bits/stdc++.h>
using namespace std;
const pair < int , int > DD[] = {{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};
# define fi cin
# define fo cout
# define x first
# define y second
# define ll long long
# define IOS ios_base :: sync_with_stdio(0);cin.tie(0)
# define p(v) cerr << #v << " = " << v << '\n'
# define p2(v) cerr << #v << " = " << (complex < __typeof(v.x) > (v.x,v.y)) << '\n'
# define vi vector < int >
# define vl vector < ll >
# define pll pair < ll , ll >
# define pii pair < int , int >
# define mp make_pair
# define db long double
# define fail puts("-1")
# define yes puts("YES")
# define no puts("NO")
# define PP puts("Possible")
# define II puts("Impossible")
# define vii vector < pii >
# define vll vector < ll >
# define pb push_back
# define pdd pair < db , db >
# define CF
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
int main(void)
{
#ifdef CF
freopen("infasuratoare.in","r",stdin);
freopen("infasuratoare.out","w",stdout);
#endif // CF
srand(time(0));
fo << fixed << setprecision(7);
cerr << fixed << setprecision(7);
static pdd s[1 << 18];
int n;
IOS;
fi>>n;
for (int i = 1;i <= n;++i)
fi>>s[i].x>>s[i].y;
int t = min_element(s + 1,s + 1 + n) - s;
swap(s[1],s[t]);
auto comp = [&](pdd a,pdd b,pdd c)
{
return (b.x - a.x) * (c.y - a.y) <= (c.x - a.x) * (b.y - a.y);
};
sort(s + 2,s + 1 + n,[&](pdd a,pdd b)
{
return comp(s[1],a,b);
});
static int p[1 << 17];
int sz;
p[sz = 1] = 1;
for (int i = 2;i <= n;++i)
{
while (sz >= 2 && comp(s[i],s[p[sz]],s[p[sz-1]]))
--sz;
p[++sz] = i;
}
fo << sz << '\n';
for (int i = 1;i <= sz;++i)
fo << s[p[i]].x << ' ' << s[p[i]].y << '\n';
cerr << "Time elapsed :" << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
return 0;
}