Cod sursa(job #3292682)

Utilizator TzepuAndrei Tzepu Data 8 aprilie 2025 22:50:04
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 kb
#include <bits/stdc++.h>

using namespace std;

#define MAX 100005

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


struct pct {
    int x,y;
} v[MAX];
int stiva[MAX];

long long cross(const pct &a,const pct &b,const pct &c) {
    return (long long)(b.x-a.x)*(c.y-a.y)-(long long)(b.y-a.y)*(c.x-a.x);
}

bool cmp(const pct &a,const pct &b) {
    long long c=cross(v[1],a,b);
    if(c==0) {
        long long da=(long long)(a.x-v[1].x)*(a.x-v[1].x)+(a.y-v[1].y)*(a.y-v[1].y);
        long long db=(long long)(b.x-v[1].x)*(b.x-v[1].x)+(b.y-v[1].y)*(b.y-v[1].y);
        return da<db;
    }
    return c>0;
}
int main()
{
    int n;
    in >> n;
    for (int i=1; i<=n; i++) {
        in >> v[i].x >> v[i].y;
    }
    int pi=1;
    ///gasim punctul cu y minim (si, in caz de egalitate, cu x minim)
    for(int i=2; i<=n; i++) {
        if(v[i].y<v[pi].y||(v[i].y==v[pi].y && v[i].x<v[pi].x)){
            pi=i;
        }
    }
    swap(v[1],v[pi]);
    sort(v+2,v+n+1,cmp);
    stiva[1]=1;
    stiva[2]=2;
    int cnt=2;
    for (int i=3; i<=n; i++) {
        while(cnt>=2 && cross(v[stiva[cnt-1]],v[stiva[cnt]],v[i])<=0){
            cnt--;
        }
        stiva[++cnt]=i;
    }
    int start=1;
    out << cnt << '\n';
    for (int i=0; i<cnt; i++) {
        int idx=stiva[(start+i-1)%cnt+1];
        out << v[idx].x << " " << v[idx].y << '\n';
    }
    return 0;
}