Pagini recente » Cod sursa (job #281388) | Cod sursa (job #2157851) | Cod sursa (job #2352048) | Cod sursa (job #1483285) | Cod sursa (job #2040606)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
#define oo (1 << 30)
using namespace std;
typedef pair<double, double> point;
vector<point> points, sol;
point origin(oo, oo);
void read() {
int n;
unsigned int pos;
double x, y;
ifstream in("infasuratoare.in");
in >> n;
for (int i = 1; i <= n; i++) {
in >> x >> y;
if ((origin.first - x > 1e-12) || ((abs(origin.first - x) < 1e-12) && (origin.second - y > 1e-12))) {
origin = make_pair(x, y);
pos = i - 1;
}
points.push_back(make_pair(x, y));
}
swap(points[0], points[pos]);
in.close();
}
inline double cross_product(const point& origin, const point& fp, const point& sp) {
return (fp.first - origin.first) * (sp.second - origin.second) - (fp.second - origin.second) * (sp.first - origin.first);
}
bool compare_points(const point& fp, const point& sp) {
if (cross_product(origin, fp, sp) > 1e-12)
return true;
return false;
}
int main() {
read();
sort(points.begin() + 1, points.end(), compare_points);
point aux;
for (unsigned int i = 0; i < points.size(); i++) {
sol.push_back(points[i]);
while (sol.size() > 2 && cross_product(sol[sol.size() - 3], sol[sol.size() - 2], sol[sol.size() - 1]) < 1e-12) {
aux = sol.back();
sol.pop_back();
sol.pop_back();
sol.push_back(aux);
}
}
ofstream out("infasuratoare.out");
out << sol.size() << "\n";
out << setprecision(6) << fixed;
for (unsigned int i = 0; i < sol.size(); i++)
out << sol[i].first << " " << sol[i].second << "\n";
out.close();
return 0;
}