Pagini recente » Cod sursa (job #1342700) | Cod sursa (job #3178683) | Cod sursa (job #1665571) | Cod sursa (job #2986387) | Cod sursa (job #2744460)
#include <fstream>
#include <algorithm>
#include <vector>
#include <iomanip>
#define ld long double
#define pi std::pair<ld, ld>
#define x first
#define y second
const int N = 12e4 + 5;
const ld eps = 1e-12;
std::ifstream fin("infasuratoare.in");
std::ofstream fout("infasuratoare.out");
pi v[N];
std::vector<int>hull;
bool viz[N];
ld cp(pi a, pi b, pi c) {
return (a.x*b.y+b.x*c.y+c.x*a.y-a.y*b.x-b.y*c.x-c.y*a.x < eps);
}
int main() {
int n, dir = 1;
fin>>n;
for(int i=1;i<=n;i++)
fin>>v[i].y>>v[i].x;
std::sort(v+1, v+n+1);
hull.push_back(1), hull.push_back(2), viz[2] = true;
for(int i=3;i;i+=dir) {
while(hull.size()>=2 and !cp(v[hull[hull.size()-2]], v[hull.back()], v[i])) viz[hull.back()] = false, hull.pop_back();
hull.push_back(i), viz[i] = true;
if(i==n) dir=-1;
}
hull.pop_back();
fout<<hull.size()<<"\n";
for(int i:hull) fout<<std::fixed<<" "<<std::setprecision(12)<<v[i].y<<" "<<v[i].x<<"\n";
}