Pagini recente » Cod sursa (job #1161989) | Cod sursa (job #1540104) | Cod sursa (job #1866579) | Cod sursa (job #3146177) | Cod sursa (job #3291516)
#include <fstream>
#include <math.h>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const double oo = 0x3f3f3f3f;
const double eps = 1e-12;
struct point
{
double x, y;
};
vector<point> v;
int n;
inline double determ(const point &a, const point &b, const point &c)
{
return a.x * b.y + b.x * c.y + c.x * a.y - a.y * b.x - b.y * c.x - c.y * a.x;
}
inline bool cmp(const point &a, const point &b)
{
return determ(v[0], a, b) < 0;
}
int main()
{
point a, left;
int index = 0;
left = {oo, oo};
fin >> n;
for (int i = 0; i < n; ++i)
{
fin >> a.x >> a.y;
v.push_back(a);
if (a.x < left.x || (abs(a.x - left.x) < eps && a.y < left.y))
{
left = a;
index = i;
}
}
swap(v[0], v[index]);
sort(v.begin() + 1, v.end(), cmp);
vector<point> st;
st.push_back(v[0]);
st.push_back(v[1]);
for (int i = 2; i < n; ++i)
{
while (st.size() > 1 && determ(st[st.size() - 2], st[st.size() - 1], v[i]) > 0)
st.pop_back();
st.push_back(v[i]);
}
fout << st.size() << '\n';
fout << fixed << setprecision(12);
for (int i = st.size() - 1; i >= 0; --i)
fout << st[i].x << " " << st[i].y << '\n';
return 0;
}