Cod sursa(job #3139128)

Utilizator Luca07Nicolae Luca Luca07 Data 25 iunie 2023 15:39:15
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.23 kb
#include <fstream>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;

ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");

struct Point {
    double x, y;
};
vector<Point> vx1, vy1,vx2,vy2;

map<pair<double, double>, bool> used;
vector<pair<double, double>> res;

int main()
{
    double i, j, n, x, y;
    
    cin >> n;
    for (i = 0; i < n; i++) {
        cin >> x >> y;
        vx1.push_back({ x,y });
        vy1.push_back({ x,y });
        vx2.push_back({ x,y });
        vy2.push_back({ x,y });
    }

    sort(vx1.begin(), vx1.end(), [](auto p1, auto p2) {
        if (p1.x == p2.x) return p1.y < p2.y;  
        return p1.x > p2.x; 
     });
    sort(vy1.begin(), vy1.end(), [](auto p1, auto p2) {
        if (p1.y == p2.y)
            return p1.x < p2.x;
        return p1.y < p2.y;
    });

    sort(vx2.begin(), vx2.end(), [](auto p1, auto p2) {
        if (p1.x == p2.x) return p1.y > p2.y;
        return p1.x < p2.x;
        });
    sort(vy2.begin(), vy2.end(), [](auto p1, auto p2) {
        if (p1.y == p2.y)
            return p1.x > p2.x;
        return p1.y > p2.y;
        });

    i = 0;
    j = 0;
    while (i < n && vy1[j].y == vy1[i].y) {
        pair<double, double> p = { vy1[i].x,vy1[i].y };
        res.push_back(p);
        used[p] = true;
        i++;
    }


    i = 0;
    j = 0;
    while (i < n && vx1[j].x == vx1[i].x) {
        pair<double, double> p = { vx1[i].x,vx1[i].y };
        i++;
        if (used[p])
            continue;
        res.push_back(p);
        used[p] = true;
    }

    i = 0;
    j = 0;
    while (i < n && vy2[j].y == vy2[i].y) {
        pair<double, double> p = { vy2[i].x,vy2[i].y };
        i++;
        if (used[p])
            continue;
        res.push_back(p);
        used[p] = true;
    }

    i = 0;
    j = 0;
    while (i < n && vx2[j].x == vx2[i].x) {
        pair<double, double> p = { vx2[i].x,vx2[i].y };
        i++;
        if (used[p]) 
            continue;
            res.push_back(p);
            used[p] = true;
        }

    cout << res.size() << "\n";
    for (auto p : res) {
        cout << p.first << " " << p.second << "\n";
    }
    return 0;
}