Cod sursa(job #2539699)

Utilizator mariamirabella2Bucur-Sabau Maria-Mirabela mariamirabella2 Data 6 februarie 2020 10:26:19
Problema Infasuratoare convexa Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.02 kb
#include <fstream>
#include <algorithm>
#include <iomanip>

using namespace std;

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

pair <double,double>p[500005],v[500005];
int top,n,ll,m;
double minix=1000000009,miniy=1000000009;

int semn(double ax,double ay,double bx,double by,double cx,double cy){
    double arie;
    arie=(ax-bx)*(ay-cy)-(ay-by)*(ax-cx);
    if(arie<0){
        return -1;
    }
    else
        return 1;
}

bool cmp(pair<double,double>a,pair<double,double>b){
    return (a.second*b.first<b.second*a.first);
}

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>p[i].first>>p[i].second;
        if(p[i].second<miniy){
            minix=p[i].first;
            miniy=p[i].second;
        }
        else{
            if(p[i].second==miniy){
                if(p[i].first<minix){
                    minix=p[i].first;
                }
            }
        }
    }
    for(int i=1;i<=n;i++){
        p[i].first-=minix;
        p[i].second-=miniy;
        if(p[i].first!=0 || p[i].second !=0)
            p[++m]=p[i];
    }
    n=m;
    /*v[1].first=minix;
    v[1].second=miniy;
    v[n+1].first=minix;
    v[n+1].second=miniy;
    */
    sort(p+1,p+n+1,cmp);
    p[n+1]=p[1];
    v[1].first=0;
    v[1].second=0;
    v[2].first=p[1].first;
    v[2].second=p[1].second;
    v[3].first=p[2].first;
    v[3].second=p[2].second;
    top=3;
    for(int i=3;i<=n+1;i++){
        while(semn(v[top-2].first,v[top-2].second,v[top-1].first,v[top-1].second,v[top].first,v[top].second)!=semn(v[top-1].first,v[top-1].second,v[top].first,v[top].second,p[i].first,p[i].second)){
            v[top].first=0;
            v[top].second=0;
            top--;
        }
        top++;
        v[top].first=p[i].first;
        v[top].second=p[i].second;
    }
    top--;
    cout<<top<<'\n';
    for(int i=1;i<=top;i++,cout<<'\n'){
        cout<<setprecision(12)<<v[i].first+minix<<" "<<setprecision(12)<<v[i].second+miniy;
    }
    return 0;
}