Pagini recente » Borderou de evaluare (job #768045) | Cod sursa (job #696744) | Cod sursa (job #1796272) | Cod sursa (job #1073984) | Cod sursa (job #1576842)
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#define MAXN 120100
using namespace std;
struct pct
{
double x, y;
pct(double x = 0, double y = 0) : x(x), y(y) { }
bool operator()(pct e, pct f)
{
if (e.x != f.x)
return e.x < f.x;
return e.y < f.x;
}
};
pct a[MAXN];
int n;
void citire()
{
double x, y;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%lf %lf\n", &x, &y);
a[i] = pct(x, y);
}
sort(a+1, a+1+n, pct());
}
vector<pct> st;
double det(pct e, pct f, pct g)
{
return e.x * f.y + f.x * g.y + g.x * e.y -
(g.x * f.y + f.x * e.y + e.x * g.y);
}
void update (pct p)
{
int last = st.size()-1;
while (true)
if (last == 0 || det(st[last-1], st[last], p) >= 0) {
if (det(st[last-1], st[last], p) != 0)
st.push_back(p);
break;
}
else
st.pop_back(), last--;
}
void solve()
{
st.push_back(a[1]);
st.push_back(a[2]);
for (int i = 3; i <= n; i++) {
update(a[i]);
}
for (int i = n-1; i >= 1; i--) {
update(a[i]);
}
st.pop_back();
printf("%d\n", st.size());
for (int i = 0, t = st.size(); i <t; i++)
printf("%lf %lf\n", st[i].x, st[i].y);
}
int main()
{
freopen("infasuratoare.in", "r", stdin);
freopen("infasuratoare.out", "w", stdout);
citire();
solve();
return 0;
}