Pagini recente » Cod sursa (job #2338007) | Cod sursa (job #955012) | Cod sursa (job #1538590) | Cod sursa (job #2378768) | Cod sursa (job #1456123)
#include <bits/stdc++.h>
using namespace std;
typedef long long var;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
typedef pair<double, double> Point;
#define x first
#define y second
vector<Point> Points, Up, Dw;
#define UpS Up.size()
#define DwS Dw.size()
#define det(A, B, C) (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x)
void Hull() {
sort(Points.begin(), Points.end());
for(auto &P : Points) {
while(UpS >= 2 && det(Up[UpS-2], Up[UpS-1], P) >= 0)
Up.pop_back();
Up.push_back(P);
while(DwS >= 2 && det(Dw[DwS-2], Dw[DwS-1], P) <= 0)
Dw.pop_back();
Dw.push_back(P);
}
}
void Afis() {
Dw.pop_back();
reverse(Up.begin(), Up.end());
Up.pop_back();
fout<<fixed<<setprecision(12)<<UpS+DwS<<'\n';
for(auto &P : Dw) fout<<P.x<<" "<<P.y<<'\n';
for(auto &P : Up) fout<<P.x<<" "<<P.y<<'\n';
}
int main() {
var n; double x, y;
fin>>n;
while(n--) {
fin>>x>>y;
Points.emplace_back(x, y);
}
Hull();
Afis();
return 0;
}