Pagini recente » Cod sursa (job #1135527) | Cod sursa (job #726164) | Cod sursa (job #3264887) | Cod sursa (job #1529030) | Cod sursa (job #492458)
Cod sursa(job #492458)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
const char iname[] = "infasuratoare.in";
const char oname[] = "infasuratoare.out";
int turnsRight(pair <double, double> a, pair <double, double> b, pair <double, double> c) {
b.first -= a.first, b.second -= a.second;
c.first -= a.first, c.second -= a.second;
return (b.first * c.second - b.second * c.first) < 0;
}
int main(void) {
int n; double x, y;
vector < pair <double, double> > points;
ifstream in(iname);
in >> n;
for (int i = 0; i < n; ++ i)
in >> x >> y, points.push_back(make_pair(x, y));
in.close();
sort(points.begin(), points.end());
vector < pair <double, double> > stk;
stk.push_back(points[0]), stk.push_back(points[1]);
for (int i = 2; i < (int) points.size(); ++ i) {
while (stk.size() > 1 && turnsRight(stk[stk.size() - 2], stk[stk.size() - 1], points[i]))
stk.pop_back();
stk.push_back(points[i]);
}
for (int i = (int) points.size() - 2; i >= 0; -- i) {
while (stk.size() > 1 && turnsRight(stk[stk.size() - 2], stk[stk.size() - 1], points[i]))
stk.pop_back();
stk.push_back(points[i]);
}
stk.pop_back();
ofstream out(oname);
out << stk.size() << '\n';
for (int i = 0; i < (int) stk.size(); ++ i)
out << stk[i].first << ' ' << stk[i].second << '\n';
out.close();
return 0;
}