Cod sursa(job #2539343)

Utilizator DanutAldeaDanut Aldea DanutAldea Data 5 februarie 2020 20:12:17
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.49 kb
#include <fstream>
#include <iostream>
#include <algorithm>
#include <iomanip>
#define x first
#define y second
using namespace std;

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

int n,i,j,k;
pair <double,double> v[120001],s[120001];

double det(pair<double,double> a, pair<double,double> b, pair<double,double> c){
    return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}

bool cmp(const pair<double,double> &a, const pair<double,double> &b){
    double d=det(make_pair(0.0,0.0),a,b);
    if(d!=0)
        return d>0;

    return a.x*a.x + a.y*a.y > b.x*b.x + b.y*b.y;
}

bool desc(const pair<double,double> &a, const pair<double,double> &b){
    return a.x<b.x;
}

int main(){
    fin>>n>>v[1].x>>v[1].y;
    for(i=2;i<=n;i++){
        fin>>v[i].x>>v[i].y;
        if(v[i].y<v[1].y)
            swap(v[1],v[i]);
        else
            if(v[i].y==v[1].y && v[i].x<v[1].x)
                swap(v[1],v[i]);
    }

    v[0]=v[1];
    for(i=1;i<=n;i++){
        v[i].x-=v[0].x;
        v[i].y-=v[0].y;
    }

    sort(v+2,v+n+1,cmp);

    for(i=3;i<=n;i++)
        if(det(v[1],v[2],v[i])!=0)
            break;

    sort(v+2,v+i,desc);

    s[1]=v[1];
    s[2]=v[2];
    k=2;

    for(i=3;i<=n;i++){
        while(k>2 && det(s[k-1],s[k],v[i])<0)
            k--;
        s[++k]=v[i];
    }

    fout<<k<<"\n";
    for(i=1;i<=k;i++)
        fout<<setprecision(6)<<fixed<<s[i].x+v[0].x<<" "<<s[i].y+v[0].y<<"\n";

    return 0;
}