Pagini recente » Cod sursa (job #2982173) | Cod sursa (job #3005194) | Cod sursa (job #3165209) | Borderou de evaluare (job #1750863) | Cod sursa (job #1456177)
#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
struct DynamicHull {
typedef double T;
typedef pair<T, T> Point;
#define x first
#define y second
#define det(A, B, C) 1LL * (B.x - A.x) * (C.y - A.y) - 1LL * (B.y - A.y) * (C.x - A.x)
set<Point> Up, Dw;
set<Point>::iterator aux, cur, pred, succ;
static bool bad(set<Point> &Set, set<Point>::iterator it) {
if(it == Set.begin()) return false;
if(++it == Set.end()) return false;
auto C = *it--, B = *it--, A = *it;
return det(A, B, C) <= 0;
}
void chk_succ(set<Point> &Set) {
succ = cur; succ++;
if(succ == Set.end()) return;
while(bad(Set, succ))
Set.erase(aux = succ++);
}
void chk_pred(set<Point> &Set) {
if(cur == Set.begin()) return;
pred = cur; pred--;
while(bad(Set, pred))
Set.erase(aux = pred--);
}
void ins(Point P, set<Point> &Set) {
cur = Set.insert(P).first;
if(Set.size() <= 2) return;
if(bad(Set, cur)) { Set.erase(cur); return; }
chk_pred(Set);
chk_succ(Set);
}
void insertPoint(T a, T b) {
ins(Point(a, b), Up);
ins(Point(-a, -b), Dw);
}
#undef first
#undef second
#undef det
};
DynamicHull H;
void Afis() {
vector<Point> UpV(H.Up.begin(), H.Up.end());
vector<Point> DwV(H.Dw.begin(), H.Dw.end());
UpV.pop_back();
DwV.pop_back();
fout<<fixed<<setprecision(10)<<UpV.size()+DwV.size()<<'\n';
for(auto P : UpV) {fout<<P.x<<" "<<P.y<<'\n';}
for(auto P : DwV) {fout<<-P.x<<" "<<-P.y<<'\n';}
}
int main() {
var n;
double x, y;
fin>>n;
while(n--) {
fin>>x>>y;
H.insertPoint(x, y);
}
Afis();
return 0;
}