Pagini recente » Cod sursa (job #3222670) | Cod sursa (job #1476157) | Cod sursa (job #2837884) | Cod sursa (job #2774235) | Cod sursa (job #1546187)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
const int nMax = 120010;
int n;
struct punct {
double x, y;
};
punct v[nMax];
vector<punct> l1, l2;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
double det(punct p, punct q, punct r) {
return (q.x - p.x)*(r.y - p.y) - (r.x - p.x)*(q.y - p.y);
}
bool vd(int d) {
return d < 0;
}
bool vs(int d) {
return d > 0;
}
void scan(bool (*vc)(int), vector<punct> &l) {
l.push_back(v[0]);
l.push_back(v[1]);
for (int i = 2; i < n; ++i) {
while ( l.size() > 1 && vc(det( l[l.size()-1], l[l.size() - 2], v[i] )) ) {
l.erase(l.begin() + l.size() - 1);
}
l.push_back(v[i]);
}
}
bool comp(punct a, punct b) {
if (a.x == b.x) {
return a.y < b.y;
}
return a.x < b.x;
}
int main() {
in >> n;
for (int i = 0; i < n; ++i) {
in >> v[i].x >> v[i].y;
}
sort(v, v + n, comp);
scan(vd, l1);
scan(vs, l2);
bool primu = false, ultimu = false;
if (l1[l1.size() - 1].x == l2[l2.size() - 1].x && l1[l1.size() - 1].y == l2[l2.size() -1].y) {
primu = true;
}
if (l1[0].x == l2[0].x && l1[0].y == l2[0].y) {
ultimu = true;
}
out << l1.size() + l2.size() - primu - ultimu << '\n';
for (vector<punct>::iterator it = l1.begin(); it != l1.end(); ++it) {
out << it -> x << ' ' << it -> y << '\n';
}
for (vector<punct>::iterator it = l2.end() - 2; it != l2.begin(); --it) {
out << it -> x << ' ' << it -> y << '\n';
}
return 0;
}