Cod sursa(job #3311126)

Utilizator Dia3141Costea Diana Stefania Dia3141 Data 19 septembrie 2025 18:06:39
Problema Infasuratoare convexa Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.61 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#define nmax 120001
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");
int n,poz=1,vf;
pair<double,double>p[nmax],s[nmax];
double det(double x1,double y1,double x2,double y2,double x3,double y3){
    return (x2-x1)*(y3-y1)-(x3-x1)*(y2-y1);
}
bool cmp(const pair<double,double>& a,const pair<double,double>& b){
    double d=det(0,0,a.first,a.second,b.first,b.second);
    if(d==0)
        return a.first*a.first+a.second*a.second>b.first*b.first+b.second*b.second;
    return d>0;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>p[i].first>>p[i].second;
        if(p[i].first<p[poz].first||(p[i].first==p[poz].first&&p[i].second<p[poz].second))
            poz=i;
    }
    if(poz!=1)
        swap(p[poz],p[1]);
    p[0]=p[1];
    for(int i=1;i<=n;i++)
        p[i].first-=p[0].first,p[i].second-=p[0].second;
    sort(p+2,p+n+1,cmp);
    poz=3;
    for(;poz<=n;poz++)
        if(det(p[1].first,p[1].second,p[2].first,p[2].second,p[poz].first,p[poz].second)!=0)
            break;
    poz--;
    for(int i=2;i<=poz;i++,poz--)
        swap(p[i],p[poz]);
    for(int i=1;i<=n;i++){
        while(vf>1&&det(s[vf-1].first,s[vf-1].second,s[vf].first,s[vf].second,p[i].first,p[i].second)<0)
            vf--;
        s[++vf]=p[i];
    }
    for(int i=1;i<=vf;i++)
        s[i].first+=p[0].first,s[i].second+=p[0].second;
    sort(s+1,s+vf+1,cmp);
    cout<<vf<<'\n';
    for(int i=1;i<=vf;i++)
        cout<<fixed<<setprecision(6)<<s[i].first<<" "<<s[i].second<<'\n';
    return 0;
}