Pagini recente » Cod sursa (job #3358597) | Monitorul de evaluare | Cod sursa (job #3358912) | Monitorul de evaluare | Cod sursa (job #3357691)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
struct Punct {
double x, y;
bool operator<(const Punct& altul) const {
if (x != altul.x) {
return x < altul.x;
}
return y < altul.y;
}
};
double determinant(const Punct& O, const Punct& A, const Punct& B) {
return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}
int main() {
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int nrPuncte;
if (!(fin >> nrPuncte)) return 0;
vector<Punct> puncte(nrPuncte);
for (int i = 0; i < nrPuncte; ++i) {
fin >> puncte[i].x >> puncte[i].y;
}
sort(puncte.begin(), puncte.end());//o foloim pe asta predefinita
vector<Punct> infasuratoareJos;
for (int i = 0; i < nrPuncte; ++i) {
while (infasuratoareJos.size() >= 2 && determinant(infasuratoareJos[infasuratoareJos.size() - 2], infasuratoareJos.back(), puncte[i]) <= 1e-11) {
infasuratoareJos.pop_back();
}
infasuratoareJos.push_back(puncte[i]);
}
vector<Punct> infasuratoareSus;
for (int i = nrPuncte - 1; i >= 0; --i) {
while (infasuratoareSus.size() >= 2 && determinant(infasuratoareSus[infasuratoareSus.size() - 2], infasuratoareSus.back(), puncte[i]) <= 1e-11) {
infasuratoareSus.pop_back();
}
infasuratoareSus.push_back(puncte[i]);
}
infasuratoareJos.pop_back();
infasuratoareSus.pop_back();
vector<Punct> poligonRezultat;
poligonRezultat.insert(poligonRezultat.end(), infasuratoareJos.begin(), infasuratoareJos.end());
poligonRezultat.insert(poligonRezultat.end(), infasuratoareSus.begin(), infasuratoareSus.end());
fout << poligonRezultat.size() << "\n";
fout << fixed << setprecision(6);
for (const auto& punct : poligonRezultat) {
fout << punct.x << " " << punct.y << "\n";
}
return 0;
}