Pagini recente » Cod sursa (job #3357521) | Cod sursa (job #3232568) | Cod sursa (job #3232574) | Cod sursa (job #3232569) | Cod sursa (job #3359141)
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
long long directie(double ax, double ay, double bx, double by, double cx, double cy){
long long p =(long long) (bx - ax) * (cy - ay) - (long long) (by - ay) * (cx - ax);
return p;
}
int main(){
int i, n;
fin >> n;
vector <pair<double , double>> puncte(n);
vector <pair <double, double>> stiva;
for(i = 0; i < n; i++){
fin >> puncte[i].first >> puncte[i].second;
}
sort(puncte.begin(), puncte.end());
stiva.push_back(puncte[0]);
for(i = 1; i < n; i++){
while(stiva.size() >= 2 && directie(stiva[stiva.size() - 2].first, stiva[stiva.size() - 2].second, stiva[stiva.size() - 1].first, stiva[stiva.size() - 1].second, puncte[i].first, puncte[i].second) <= 1e-12){
stiva.pop_back();
}
stiva.push_back(puncte[i]);
}
int k = stiva.size();
for(i = n - 2; i >= 0; i--){
while(stiva.size() >= k + 1 && directie(stiva[stiva.size() - 2].first, stiva[stiva.size() - 2].second, stiva[stiva.size() - 1].first, stiva[stiva.size() - 1].second, puncte[i].first, puncte[i].second) <= 1e-12){
stiva.pop_back();
}
stiva.push_back(puncte[i]);
}
fout << stiva.size() - 1 << endl;
fout << fixed << setprecision(6);
for(i = 0; i < stiva.size() - 1; i++){
fout << stiva[i].first << " " << stiva[i].second << endl;
}
fin.close();
fout.close();
return 0;
}