Pagini recente » Cod sursa (job #2651668) | Cod sursa (job #2760713) | Cod sursa (job #1483430) | Cod sursa (job #53730) | Cod sursa (job #2402054)
#include <bits/stdc++.h>
using namespace std;
double e = 1e-12;
struct po { double x, y; };
inline double cp(po a, po b, po c) { return (b.x - a.x) * (c.y - b.y) - (b.y - a.y) * (c.x - b.x); };
inline int ccw(po a, po b, po c)
{
double x = cp(a, b, c);
if(fabs(x) < e) return 0;
if(x > e) return 1;
return -1;
}
vector<po> v;
vector<int> st;
bool cmp(po a, po b) { return ccw(v[0], a, b) == 1; }
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
int n;
double x, y;
scanf("%d", &n);
scanf("%lf%lf", &x, &y), v.push_back({x, y});
for(int i = 1; i < n; i++)
{
scanf("%lf%lf", &x, &y), v.push_back({x, y});
if(y < v[0].y or (y == v[0].y and x < v[0].x)) v.pop_back(), v.push_back(v[0]), v[0] = {x, y};
}
sort(v.begin() + 1, v.end(), cmp);
v.push_back(v[0]);
st.push_back(0), st.push_back(1);
for(int i = 2; i <= n;)
{
if(ccw(v[st[st.size() - 2]], v[st[st.size() - 1]], v[i]) > 0) st.push_back(i), i++;
else st.pop_back();
}
printf("%d\n", st.size() - 1);
for(int i = 0; i < st.size() - 1; i++) printf("%lf %lf\n", v[st[i]].x, v[st[i]].y);
return 0;
}