Cod sursa(job #3343969)

Utilizator tudorhTudor Horobeanu tudorh Data 28 februarie 2026 20:10:23
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.61 kb
#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int,int>
#define ll long long


using namespace std;

ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");

const int nmax = 120001;

struct point {
    double x, y;
    bool operator< (const point&other) const {
        if (x != other.x)
            return x < other.x;
        return  y < other.y;
    }
    bool side;
} p[nmax + 1];

double Arie (point a, point b, point c) {
    return a.x * b.y + b.x * c.y + c.x * a.y - c.x * b.y - a.x * c.y - b.x * a.y;
}
vector<point>v;
int main() {
    int n;
    fin >> n;
    for (int i = 1; i <= n; i++)
        fin >> p[i].x >> p[i].y;
    sort (p + 1, p + n + 1);
    for (int i = 2; i < n; i++)
        p[i].side = (Arie (p[1], p[n], p[i]) > 0);
    v.pb (p[1]);
    for (int i = 2; i <= n; i++) {
        if (p[i].side)
            continue;
        if (v.size() == 1)
            v.pb (p[i]);
        else {
            while (v.size() >= 2 && Arie (v[v.size() - 2], p[i], v[v.size() - 1]) > 0)
                v.pop_back();
            v.pb (p[i]);
        }
    }
    int old_size=v.size()-1;
    p[1].side=1;
    for(int i=n-1;i>=1;i--){
        if(!p[i].side)
            continue;
        if(v.size()-old_size==1)
            v.pb(p[i]);
        else{
            while(v.size()-old_size>=2 && Arie(v[v.size()-2],p[i],v[v.size()-1])>0)
                v.pop_back();
            v.pb(p[i]);
        }
    }
    v.pop_back();
    fout<<fixed<<setprecision(6)<<v.size()<<'\n';
    for(point i:v)
        fout<<i.x<<' '<<i.y<<'\n';
    return 0;
}