Pagini recente » Cod sursa (job #187473) | Cod sursa (job #3211676) | Cod sursa (job #1217663) | Cod sursa (job #813193) | Cod sursa (job #2592107)
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <iterator>
#include <list>
#define inf 1e8
#define x first
#define y second
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int i, poz, h, n;
double xc, yc;
pair <double, double> start;
vector<pair<double, double>> v;
list<int> s;
double calc(pair<double, double> a, pair <double, double> b, pair <double, double> c) {
return (b.x - c.x) * (a.y - c.y) - (b.y - c.y) * (a.x - c.x);
}
bool cmp(pair<double, double> a, pair <double, double> b) {
if (calc(a, b, start) < 0)
return 1;
return 0;
}
int main() {
fin >> n;
start = { inf,inf };
for (i = 0; i < n; i++) {
fin >> xc >> yc;
v.push_back(make_pair(xc, yc));
if (xc < start.x)
start = v[i], poz = i;
else
if (v[i].x == start.x && v[i].y < start.y)
start = v[i], poz = i;
}
swap(v[0], v[poz]);
sort(v.begin()+1,v.end(), cmp);
s.push_back(0);
s.push_back(1);
for (i = 2; i < n; i++) {
if (calc(v[s.back()], v[i], v[*next(s.rbegin())]) <= 0)
s.push_back(i);
else {
while (calc(v[s.back()], v[i], v[*next(s.rbegin())]) > 0)
s.pop_back();
s.push_back(i);
}
}
fout << s.size() << "\n";
for (auto it:s)
fout << setprecision(6) << fixed << v[it].x << " " << v[it].y << "\n";
}