Pagini recente » Istoria paginii utilizator/onizuka123 | Monitorul de evaluare | Statistici Sergiu (private044) | Cod sursa (job #2069968) | Cod sursa (job #2051287)
#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <algorithm>
#define oo (1 << 30)
using namespace std;
typedef pair<double, double> point;
vector<point> points, sol;
point origin(oo, oo);
void read() {
int n;
double x, y;
ifstream in("infasuratoare.in");
for (in >> n; n; --n) {
in >> x >> y;
if (x < origin.first || (x == origin.first && y < origin.second))
origin = make_pair(x, y);
points.push_back(make_pair(x, y));
}
in.close();
}
inline double cross_product(const point& p, const point& q, const point& r) {
return (q.first - p.first) * (r.second - p.second) - (r.first - p.first) * (q.second - p.second);
}
int main() {
read();
sol.push_back(origin);
point aux(oo, oo), current = sol.back();
do {
current = sol.back();
aux = make_pair(oo, oo);
for (unsigned int i = 0; i < points.size(); i++) {
if (aux == point(oo, oo) && points[i] != current)
aux = points[i];
else if (current != points[i] && cross_product(current, aux, points[i]) < 0)
aux = points[i];
}
sol.push_back(aux);
} while (sol.front() != sol.back());
ofstream out("infasuratoare.out");
out << sol.size() - 1 << "\n";
out << setprecision(6) << fixed;
for (unsigned int i = 0; i < sol.size() - 1; i++)
out << sol[i].first << " " << sol[i].second << "\n";
out << "\n";
out.close();
return 0;
}