Pagini recente » Cod sursa (job #2144428) | Cod sursa (job #1406737) | Cod sursa (job #2362464) | Cod sursa (job #2166544) | Cod sursa (job #3224009)
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <list>
using namespace std;
using point=pair<double,double>;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
const int MAXN = 12e4;
point v[MAXN + 1];
point *O = v;
bool cmp(point &A, point &B) {
if (A.first == B.first)
return A.second < B.second;
return A.first < B.first;
}
double cmpcrossProduct(point A, point B) {
point AO = {O->first - A.first, O->second - A.second};
point OB = {B.first - O->first, B.second - O->second};
return AO.first * OB.second > AO.second * OB.first;
}
bool trigonometricOrder(point A, point B, point C) {
point AB = {B.first - A.first, B.second - A.second};
point BC = {C.first - B.first, C.second - B.second};
return AB.first * BC.second > AB.second * BC.first;
}
ostream& operator<<(ostream &os, const point &a) {
os << a.first << ' ' << a.second;
return os;
}
int main() {
ios_base::sync_with_stdio(false);
fin.tie(NULL);
fout.tie(NULL);
int n;
fin >> n;
for (int i = 0; i < n; i++)
fin >> v[i].first >> v[i].second;
sort(v, v + n, cmp);
sort(v + 1, v + n, cmpcrossProduct);
vector<point> poli;
poli.push_back(*O);
v[n] = v[0];
for (int i = 1; i < n; i++) {
while (i < n && trigonometricOrder(*poli.rbegin(), v[i], v[i + 1]))
i++;
poli.push_back(v[i]);
}
list<point> newpoli(poli.begin(), poli.end());
while (true) {
bool stop = true;
auto itr = newpoli.begin();
for (++itr; itr != newpoli.end(); itr++)
if (trigonometricOrder(*prev(itr), *itr, *next(itr))) {
itr = prev(newpoli.erase(itr));
stop = false;
}
if (stop)
break;
}
poli = vector<point>(make_move_iterator(begin(newpoli)), make_move_iterator(end(newpoli)));
reverse(poli.begin() + 1, poli.end());
fout << poli.size() << '\n';
for (point elem: poli)
fout << fixed << setprecision(14) << elem << '\n';
return 0;
}