Pagini recente » Diferente pentru reguli intre reviziile 2 si 1 | Istoria paginii utilizator/axel93 | Monitorul de evaluare | Monitorul de evaluare | Cod sursa (job #2051214)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
using namespace std;
typedef pair<double, double> point;
vector<point> points;
vector<point> inf, sup;
bool compare(const point& fp, const point& sp) {
if (fp.first < sp.first)
return true;
if (fp.first == sp.first && fp.second < sp.second)
return true;
return false;
}
void read() {
int n;
double x, y;
ifstream in("infasuratoare.in");
for (in >> n; n; --n) {
in >> 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();
sort(points.begin(), points.end(), compare);
point aux;
for (unsigned int i = 0; i < points.size(); ++i) {
inf.push_back(points[i]);
while (inf.size() >= 3 && cross_product(inf[inf.size() - 3], inf[inf.size() - 2], inf[inf.size() - 1]) <= 0) {
aux = inf.back();
inf.pop_back();
inf.pop_back();
inf.push_back(aux);
}
}
for (int i = points.size() - 1; i >= 0; --i) {
sup.push_back(points[i]);
while (sup.size() >= 3 && cross_product(sup[sup.size() - 3], sup[sup.size() - 2], sup[sup.size() - 1]) <= 0) {
aux = sup.back();
sup.pop_back();
sup.pop_back();
sup.push_back(aux);
}
}
ofstream out("infasuratoare.out");
out << inf.size() + sup.size() - 2 << "\n";
out << setprecision(6) << fixed;
for (unsigned int i = 0; i < inf.size(); ++i)
out << inf[i].first << " " << inf[i].second << "\n";
for (unsigned int i = 1; i < sup.size() - 1; ++i)
out << sup[i].first << " " << sup[i].second << "\n";
out << "\n";
out.close();
return 0;
}