Cod sursa(job #3336095)

Utilizator GliggyGligor Andrei Gliggy Data 24 ianuarie 2026 10:30:42
Problema Pachete Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
long long x,y,n,i,inf=1e9,j;
double vx=1e10,vy=1e10;
struct pct{double x,y,p,d; long long cad;};
pct a[120010];
stack<long long> s,st;
long long cad(double x,double y){if(x>=0) return 1; return 2;}
bool cmp(pct a,pct b){
    return a.cad<b.cad||a.cad==b.cad&&a.p<b.p||a.cad==b.cad&&a.p==b.p&&a.d>b.d;
}
double det(long long x,long long y,long long z){
    return a[x].x*(a[y].y-a[z].y)+a[x].y*(a[z].x-a[y].x)+a[y].x*a[z].y-a[z].x*a[y].y;
}
int main(){
    fin>>n;
    for(i=1;i<=n;i++){
        fin>>a[i].x>>a[i].y;
        if(vy>a[i].y||vy==a[i].y&&vx>a[i].x) vx=a[i].x,vy=a[i].y;
    }
    for(i=1;i<=n;i++){
        a[i].x-=vx,a[i].y-=vy;
        if(a[i].x==0&&a[i].y==0) a[i].cad=-1,a[i].p=-1;
        else{
            a[i].cad=cad(a[i].x,a[i].y);
            a[i].d=pow(1.0*a[i].x,2)+pow(1.0*a[i].y,2);
            a[i].p=(a[i].x==0?inf:1.0*a[i].y/a[i].x);
        }
    }
    sort(a+1,a+n+1,cmp);
    s.push(1); s.push(2);
    for(i=3;i<=n;i++){
        // REPARARE: Verificam dimensiunea stivei inainte de a accesa y
        while(s.size()>=2){
            x=s.top(); s.pop();
            y=s.top();
            if(det(y,x,i)>1e-11){ // Folosim epsilon pentru precizie
                s.push(x);
                break;
            }
        }
        s.push(i);
    }
    fout<<s.size()<<'\n';
    while(!s.empty()) st.push(s.top()),s.pop();
    while(!st.empty()) fout<<fixed<<setprecision(6)<<a[st.top()].x+vx<<' '<<a[st.top()].y+vy<<'\n',st.pop();
    return 0;
}