Cod sursa(job #2776226)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 18 septembrie 2021 22:18:55
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.88 kb
#include<fstream>
#include<iomanip>
using namespace std;
ifstream F("infasuratoare.in");
ofstream G("infasuratoare.out");
#define N 120001
int n,p,i,t,s[N];
struct P {
	double x,y;
};
P v[N],r,u[N];
#define A(a,b,c) ((b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y))
void M(int l,int r)
{
    if(l==r)
        return;
    int i,j,k,m=(l+r)/2;
    for(M(l,m),M(m+1,r),i=k=l,j=m+1;i<=m||j<=r;)
    	u[k++]=(j>r||(i<=m&&A(v[1],v[i],v[j])<0))?v[i++]:v[j++];
    for(i=l;i<=r;++i)
        v[i]=u[i];
}
int main()
{
    F>>n;
    for(p=i=1;i<=n;++i)
        F>>v[i].x>>v[i].y,p=v[i].x<v[p].x||(v[i].x==v[p].x&&v[i].y<v[p].y)?i:p;
    for(r=v[1],v[1]=v[p],v[p]=r,M(2,n),s[++t]=1,i=2;i<=n;++i) {
        for(;t>1&&A(v[s[t-1]],v[s[t]],v[i])>0;--t);
        s[++t]=i;
    }
    for(G<<t<<"\n";t;--t)
        G<<setprecision(6)<<fixed<<v[s[t]].x<<" "<<v[s[t]].y<<"\n";
    return 0;
}