Pagini recente » Cod sursa (job #3138690) | Cod sursa (job #1978815) | Cod sursa (job #3190039) | Cod sursa (job #1155615) | Cod sursa (job #2720556)
#include <fstream>
#include <vector>
#include <iomanip>
#include <algorithm>
#define ld long double
#define pi std::pair<ld, ld>
std::ifstream fin("infasuratoare.in");
std::ofstream fout("infasuratoare.out");
const ld eps = 1e-12;
ld cross(pi a, pi b, pi c) {
return (c.second * (b.first-a.first) - c.first * (b.second-a.second) + b.second*a.first - b.first*a.second < eps);
}
int main() {
int n, dir = 1;
fin>>n;
std::vector<pi>vec(n);
std::vector<int> hull = {0, 1}, viz(n, 0);
for(int i=0;i<n;i++) fin>>vec[i].second>>vec[i].first;
std::sort(vec.begin(), vec.end());
viz[1] = 1;
for(int i=2;i>=0;i+=dir) if(!viz[i]){
while(hull.size()>=2 and !cross(vec[hull[hull.size()-2]], vec[hull.back()], vec[i])) viz[hull.back()] = 0, hull.pop_back();
hull.push_back(i), viz[hull.back()] = 1;
if(hull.back() == n - 1) dir = -1;
}
hull.pop_back();
fout<<hull.size()<<'\n';
for(int ind:hull) fout<<std::fixed<<std::setprecision(12)<<vec[ind].second<<" "<<vec[ind].first<<'\n';
}