Cod sursa(job #3271923)

Utilizator AlekuwAlexandru Stefan Pascut Alekuw Data 27 ianuarie 2025 20:01:36
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#include <fstream>
#include <cmath>
#include <iomanip>
#include <algorithm>
using namespace std;
//ifstream cin("/Users/alekuw/Desktop/informatica/informatica/Products/Debug/date.in");
//ofstream cout("/Users/alekuw/Desktop/informatica/informatica/Products/Debug/date.out");
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
const double eps=1.e-12;
const double inf=1e9;
struct point {
    double x,y;
};
point p[120010],LL;
int h[120010];
int ccw(point p1, point p2, point p3){
    double cp;
    cp=(p2.x-p1.x)*(p3.y-p2.y)-(p2.y-p1.y)*(p3.x-p2.x);
    if(fabs(cp)<eps) return 0;
    if(cp>=eps) return 1;
    return -1;
}
bool cmp(point p1, point p2){
    return ccw(LL,p1,p2)>0;
}

int main() {
    int n,i,top;
    cin>>n;
    cin>>p[0].x>>p[0].y;
    for(i=1;i<n;++i){
        cin>>p[i].x>>p[i].y;
        if(p[i].y-p[0].y<=-eps ||(fabs(p[i].y-p[0].y)<eps && p[i].x-p[0].x<=-eps)){
            swap(p[0],p[i]);
        }
    }
    LL=p[0];
    sort(p+1,p+n,cmp);
    p[n]=p[0];
    h[0]=0;
    h[1]=1;
    i=2;
    top=1;
    while(i<=n){
        if(ccw(p[h[top-1]],p[h[top]],p[i])>0){
            h[++top]=i;
            i++;
        }
        else{
            top--;
        }
    }
    
    
        cout<<top<<'\n';
        cout<<fixed<<showpoint;
    for(i=0;i<top;++i){
        cout<<setprecision(6)<<p[h[i]].x<<" "<<p[h[i]].y<<'\n';
    }
       
    
    
    return 0;
}