Pagini recente » Cod sursa (job #1937433) | Cod sursa (job #1948683) | Cod sursa (job #1948712) | Cod sursa (job #1937448) | Cod sursa (job #1948686)
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream cin ("infasuratoare.in" );
ofstream cout("infasuratoare.out");
struct pt
{
double x, y;
} MinPt;
vector <pt> a, h;
void read()
{
int n;
pt p;
cin >> n;
cin >> MinPt.x >> MinPt.y;
a.push_back(MinPt);
for (int i = 1; i < n; i++)
{
cin >> p.x >> p.y;
a.push_back(p);
if (p.x < MinPt.x || (p.x == MinPt.x && p.y < MinPt.y)) MinPt = p;
}
//cout << MinPt.x << ' ' << MinPt.y << '\n' << '\n' << '\n';
}
double det(pt a, pt b, pt c)
{
return a.x*(b.y - c.y) + b.x*(c.y - a.y) + c.x*(a.y - b.y);
}
bool f_4_compare(pt a, pt b)
{
return det(MinPt, a, b) > 0;
}
void ch()
{
h.push_back(a[0]);
h.push_back(a[1]);
for (size_t i = 2; i < a.size(); i++)
{
h.push_back(a[i]);
int q = h.size() - 1;
while ( det(h[q - 2], h[q - 1], h[q]) < 0)
{
q = h.size() - 1;
pt x = h[q];
h.pop_back();
h.back() = x;
}
}
h.push_back(MinPt);
}
void write()
{
cout << h.size() << '\n';
for (size_t i = 0; i < h.size(); i++)
cout << setprecision(13) << h[i].x << ' ' << h[i].y << '\n';
}
int main()
{
read();
sort(a.begin(), a.end(), f_4_compare);
// for (size_t i = 0; i < a.size(); i++)
// cout << a[i].x << ' ' << a[i].y << '\n';
// cout << '\n' << '\n' << '\n';
ch();
write();
return 0;
}