Cod sursa(job #2506377)

Utilizator pasoi_stefanPasoi Stefan pasoi_stefan Data 7 decembrie 2019 22:13:03
Problema Infasuratoare convexa Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include<fstream>
#include<cmath>
#include<algorithm>
#include<iomanip>
using namespace std;
ifstream cin("infasuratoare.in");
ofstream cout("infasuratoare.out");

int n,tp;
struct punct{

    double x,y,angle;

} a[120005];
int st[120005];

double Angle[120005];

int isLeft(const punct &P,const punct &Q,const punct &R){

    return ((Q.x-P.x)*(R.y-P.y)-(Q.y-P.y)*(R.x-P.x)>0);

}

int cmp(const punct &P,const punct &Q){

    return P.angle<Q.angle;

}



int main(){

    cin>>n;

    for(int i=1;i<=n;i++)
        cin>>a[i].x>>a[i].y;

    for(int i=2;i<=n;i++)
        if(a[1].x>a[i].x ||
           a[1].x==a[i].x && a[1].y>a[i].y)
                swap(a[1],a[i]);

    for(int i=2;i<=n;i++){

        double x=a[i].x-a[1].x;
        double y=a[i].y-a[1].y;
        double L=sqrt(x*x+y*y);

        a[i].angle=acos(-y/L);

    }

    sort(a+2,a+n+1,cmp);
    st[1]=1; st[2]=2;
    tp=2;
    for(int i=3;i<=n;i++){

        while(tp>=2 && !isLeft(a[st[tp-1]],a[st[tp]],a[i])) --tp;
        st[++tp]=i;

    }

    cout<<tp<<'\n';
    for(int i=1;i<=tp;i++)
        cout<<fixed<<setprecision(6)<<a[st[i]].x<<' '<<a[st[i]].y<<'\n';

}