Pagini recente » Cod sursa (job #2234103) | Cod sursa (job #194935) | Cod sursa (job #1197122) | Cod sursa (job #299856) | Cod sursa (job #1456154)
#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
#define det(A, B, C) (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x)
set<Point> Up, Dw;
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 ins(Point P, set<Point> &Set) {
auto it = Set.insert(P).x;
if(Set.size() <= 2) return;
if(bad(Set, it)) {Set.erase(it); return;}
auto chk_succ = [&Set, &it]() {
auto succ = it; succ++;
if(succ == Set.end()) return;
while(bad(Set, succ)) {
auto aux = succ++;
Set.erase(aux);
}
};
auto chk_pred = [&Set, &it]() {
if(it == Set.begin()) return;
auto pred = it; pred--;
while(bad(Set, pred)) {
auto aux = pred--;
Set.erase(aux);
}
};
chk_succ();
chk_pred();
}
void insertPoint(double a, double b) {
ins(Point(a, b), Up);
ins(Point(-a, -b), Dw);
}
void Afis() {
vector<Point> UpV(Up.begin(), Up.end());
vector<Point> DwV(Dw.begin(), 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;
insertPoint(x, y);
}
Afis();
return 0;
}