Pagini recente » Cod sursa (job #1018990) | Cod sursa (job #1785672) | Cod sursa (job #1355733) | Rating BalanoiuAlexandru (BalanoiuAlexandru) | Cod sursa (job #1721075)
#include <bits/stdc++.h>
using namespace std;
struct punct{
double x, y; };
double cross_product(const punct& p1, const punct& p2){
return p1.x * p2.y - p2.x * p1.y; }
bool is_left_turn(const punct& p1, const punct& p2, const punct& p3){
return cross_product(punct{ p1.x - p2.x, p1.y - p2.y},
punct{ p3.x - p2.x, p3.y - p2.y }) < 0; }
auto x_cmp = [](const punct& p1, const punct& p2){
return p1.x < p2.x || (p1.x == p2.x && p1.y < p2.y); };
template <typename T>
T& sec_back(vector<T>& v){
return v[v.size()-2]; }
vector<punct> mk_half_infasuratoare(const vector<punct>& pts){
vector<punct> rez = {pts[0]};
for(int i = 1; i < pts.size(); ++i){
const auto p = pts[i];
while(rez.size() > 1 && !is_left_turn(sec_back(rez), rez.back(), p)){
rez.pop_back(); }
rez.push_back(p); }
return rez; }
vector<punct> mk_infasuratoare(vector<punct>& pts){
sort(begin(pts), end(pts), x_cmp);
vector<punct> under, over;
under.push_back(pts[0]);
over.push_back(pts[0]);
for(int i = 1; i < pts.size()-1; ++i){
const auto p = pts[i];
(is_left_turn(pts[0], pts.back(), p) ? over : under).push_back(p); }
under.push_back(pts.back());
over.push_back(pts.back());
reverse(begin(over), end(over));
auto inf_over = mk_half_infasuratoare(over),
inf_under = mk_half_infasuratoare(under);
inf_under.pop_back(), inf_over.pop_back();
inf_under.insert(end(inf_under), begin(inf_over), end(inf_over));
return inf_under; }
int main(){
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
int n;
f >> n;
vector<punct> pts(n);
for(auto& p : pts){
f >> p.x >> p.y; }
vector<punct> rez = mk_infasuratoare(pts);
g << rez.size() << '\n';
g << fixed << setprecision(6);
for(const auto p : rez){
g << p.x << ' ' << p.y << '\n'; }
return 0; }