Pagini recente » Borderou de evaluare (job #3366059) | Borderou de evaluare (job #3365399) | Cod sursa (job #3366945) | Cod sursa (job #3365504) | Cod sursa (job #3366830)
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
struct Punct {
long double x, y;
friend bool operator<(Punct a, Punct b) {
if(a.x < b.x)
return true;
if(a.x == b.x && a.y < b.y)
return true;
return false;
}
};
int n;
vector<Punct> puncte;
vector<Punct> st;
inline long double ccw(Punct o, Punct a, Punct b)
{
return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
}
inline bool cmp(Punct a, Punct b) {
return ccw(puncte[0], a, b) < 0;
}
int main() {
cin >> n;
for (int i = 0 ; i < n ; ++i) {
long double x, y;
cin >> x >> y;
puncte.push_back({x, y});
}
// pozitia celui mai stanga-jos punct
int pos = 0;
for (int i = 1 ; i < n ; ++i) {
if (puncte[i] < puncte[pos]) pos = i;
}
// il punem pe pozitia 0
swap(puncte[0], puncte[pos]);
// sortam dupa unghiuri fara el
sort(puncte.begin() + 1, puncte.end(), cmp);
// cat timp punctul de vrem sa-l adaugam cauzeaza poligonul sa fie concav, scoatem ultimul punct din infasurare
st.push_back(puncte[0]);
st.push_back(puncte[1]);
for (int i = 2 ; i < n ; ++i) {
// cat timp putem scoate si se face concav
while (st.size() >= 2 && ccw(st[st.size() - 2], st[st.size() - 1], puncte[i]) > 0) {
st.pop_back();
}
st.push_back(puncte[i]);
}
cout << st.size() << "\n";
for (int i = st.size() - 1 ; i >= 0 ; --i) {
cout << fixed << setprecision(6) << st[i].x << " " << st[i].y << "\n";
}
return 0;
}