Pagini recente » Cod sursa (job #1536227) | Cod sursa (job #2596165) | Cod sursa (job #1365329) | Cod sursa (job #2265167) | Cod sursa (job #1456121)
#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;
var UpS, DwS;
double det(Point A, Point B, Point C) {
B.x -= A.x; C.x -= A.x;
B.y -= A.y; C.y -= A.y;
return B.x * C.y - B.y * C.x;
}
void Hull() {
sort(Points.begin(), Points.end());
for(auto &P : Points) {
while(UpS >= 2 && det(Up[UpS-2], Up[UpS-1], P) >= 0) {
UpS--;
Up.pop_back();
}
UpS++;
Up.push_back(P);
while(DwS >= 2 && det(Dw[DwS-2], Dw[DwS-1], P) <= 0) {
DwS--;
Dw.pop_back();
}
DwS++;
Dw.push_back(P);
}
}
void Afis() {
fout<<fixed<<setprecision(12);
fout<<UpS+DwS-2<<'\n';
for(var i=0; i<Dw.size()-1; i++) fout<<Dw[i].first<<" "<<Dw[i].second<<'\n';
for(var i=Up.size()-1; i>0; i--) fout<<Up[i].first<<" "<<Up[i].second<<'\n';
}
int main() {
var n; double x, y;
fin>>n;
while(n--) {
fin>>x>>y;
Points.emplace_back(x, y);
}
Hull();
Afis();
return 0;
}