Pagini recente » Cod sursa (job #341547) | Cod sursa (job #586921) | Cod sursa (job #1245029) | Cod sursa (job #2777660) | Cod sursa (job #3219300)
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <stack>
#include <vector>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct punct{
long double x;
long double y;
};
vector<punct> puncte;
vector<punct> stiva_jos;
vector<punct> stiva_sus;
bool compare(punct a, punct b){
if (a.x == b.x)
return a.y <= b.y;
return a.x <= b.x;
}
long double arie(punct a, punct b, punct c){
return a.x * b.y + b.x * c.y + c.x * a.y - b.y * c.x - c.y * a.x - a.y * b.x;
}
int main(){
int n;
fin >> n;
for (int i = 0; i < n; i++){
punct z;
fin >> z.x >> z.y;
puncte.push_back(z);
}
sort(puncte.begin(), puncte.end(), compare);
stiva_jos.push_back(puncte[0]);
for (int i = 1; i < n; i++){
int sz = stiva_jos.size() - 1;
while (stiva_jos.size() >= 2 && arie(stiva_jos[sz], stiva_jos[sz - 1], puncte[i]) > 0){
stiva_jos.pop_back();
sz--;
}
stiva_jos.push_back(puncte[i]);
}
stiva_sus.push_back(puncte[0]);
for (int i = 1; i < n; i++){
int sz = stiva_sus.size() - 1;
while (stiva_sus.size() >= 2 && arie(stiva_sus[sz], stiva_sus[sz - 1], puncte[i]) < 0){
stiva_sus.pop_back();
sz--;
}
stiva_sus.push_back(puncte[i]);
}
fout << stiva_jos.size() + stiva_sus.size() - 2 << '\n';
for (int i = 0; i < stiva_jos.size() - 1; i++){
fout << fixed << setprecision(6) << stiva_jos[i].x << " ";
fout << fixed << setprecision(6) << stiva_jos[i].y << " ";
fout << '\n';
}
for (int i = stiva_sus.size() - 1; i > 0; i--){
fout << fixed << setprecision(6) << stiva_sus[i].x << " ";
fout << fixed << setprecision(6) << stiva_sus[i].y << " ";
fout << '\n';
}
return 0;
}