Cod sursa(job #3347719)

Utilizator tudorhTudor Horobeanu tudorh Data 18 martie 2026 01:38:37
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <bits/stdc++.h>
#define ll long long
#define pb push_back

using namespace std;

const int nmax=120000;

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

int n,ss[nmax+1];

struct Point{
    double x,y;
}p[nmax+1];

double det(Point a,Point b,Point c){
    return a.x*b.y+b.x*c.y+c.x*a.y-c.x*b.y-b.x*a.y-a.x*c.y;
}

bool polar_sort(Point a,Point b){
    return det(p[1],a,b)>0;
}

void read(){
    fin>>n;
    for(int i=1;i<=n;i++)
        fin>>p[i].x>>p[i].y;
}

void find_extreme(){
    int mini=1;
    for(int i=2;i<=n;i++)
        if(p[i].y<p[mini].y || (p[i].y==p[mini].y && p[i].x<p[mini].x))
            mini=i;
    swap(p[1],p[mini]);
}

void graham_scan(){
    for(int i=1;i<=n;i++){
        while(ss[0]>=2 && det(p[ss[ss[0]-1]],p[ss[ss[0]]],p[i])<0)
            ss[0]--;
        ss[++ss[0]]=i;
    }
}

void print_hull(){
    fout<<ss[0]<<'\n';
    for(int i=1;i<=ss[0];i++)
        fout<<p[ss[i]].x<<' '<<p[ss[i]].y<<'\n';
}
int main() {
    ios_base::sync_with_stdio (false);
    cin.tie (nullptr);
    read();
    find_extreme();
    sort(p+2,p+n+1,polar_sort);
    graham_scan();
    fout<<fixed<<setprecision(6);
    print_hull();
    //for(int i=1;i<=n;i++)
        //cout<<p[i].x<<' '<<p[i].y<<'\n';
    return 0;
}