Cod sursa(job #3217333)

Utilizator Alex_Mihai10Mihai Alex-Ioan Alex_Mihai10 Data 22 martie 2024 13:07:33
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#include <bits/stdc++.h>
#define MAX 120005

using namespace std;

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

struct str
{
    double x,y;
}pct[MAX];

double det(str a,str b,str c)
{
    double x1=a.x;
    double y1=a.y;
    double x2=b.x;
    double y2=b.y;
    double x3=c.x;
    double y3=c.y;
    return x1*y2+x2*y3+x3*y1-x3*y2-x2*y1-x1*y3;
}

bool cmp(str a,str b)
{
    return det(pct[1],a,b)<0;
}

str stv[MAX];

int main()
{
    int n;
    fin>>n;
    int i;
    for(i=1;i<=n;++i)
        fin>>pct[i].x>>pct[i].y;
    for(i=2;i<=n;++i)
        if(pct[i].x<pct[1].x || (pct[i].x==pct[1].x && pct[i].y<pct[1].y))
            swap(pct[i],pct[1]);
    sort(pct+2,pct+n+1,cmp);
    int vf=0;
    for(i=1;i<=n;++i)
    {
        while(vf>1 && det(stv[vf-1],stv[vf],pct[i])>0)
            --vf;
        stv[++vf]=pct[i];
    }
    fout<<vf<<'\n';
    for(i=vf;i;--i)
        fout<<fixed<<setprecision(6)<<stv[i].x<<' '<<stv[i].y<<'\n';
    return 0;
}