Pagini recente » Cod sursa (job #597757) | Monitorul de evaluare | Cod sursa (job #1347076) | Cod sursa (job #1550027) | Cod sursa (job #1577030)
#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.y;
}
};
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--;
/// Era gresit comparatorul din sortare firar sa fie....
for (int last = st.size()-1; last && det(st[last-1], st[last], p) < 0; last--)
st.pop_back();
st.push_back(p);
}
void solve()
{
st.push_back(a[1]);
for (int i = 2; 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;
}