Pagini recente » Cod sursa (job #3148874) | Cod sursa (job #87803) | Cod sursa (job #805994) | Cod sursa (job #1655054) | Cod sursa (job #1456150)
#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;
#define UpS Up.size()
#define DwS Dw.size()
bool check(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(check(Set, it)) {Set.erase(it); return;}
//cerr<<"Inserted: "<<it->x<<" "<<it->y<<'\n';
auto chk_succ = [&Set, &it]() {
auto succ = it; succ++;
if(succ == Set.end()) return;
while(check(Set, succ)) {
auto aux = succ++;
//cerr<<"Deleted: "<<aux->x<<" "<<aux->y<<'\n';
Set.erase(aux);
}
};
auto chk_pred = [&Set, &it]() {
if(it == Set.begin()) return;
auto pred = it; pred--;
while(check(Set, pred)) {
auto aux = pred--;
//cerr<<"Deleted: "<<aux->x<<" "<<aux->y<<'\n';
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';}
}
#define INF 1e9
int main() {
var n; double x, y;
fin>>n;
while(n--) {
fin>>x>>y;
insertPoint(x, y);
}
Afis();
return 0;
}