Cod sursa(job #3146754)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 22 august 2023 13:45:43
Problema Infasuratoare convexa Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.66 kb
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define N 240001
#define p pair<double,double>
int i,j,M,t;
p v[N],h[N];
bool d(p &a,p &b,p &c)
{
    return (a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x)<0;
}
int main()
{
    freopen("infasuratoare.in","r",stdin),freopen("infasuratoare.out","w",stdout),scanf("%d",&M);
    for(i=0;i<M;++i)
        scanf("%lf%lf",&v[i].x,&v[i].y);
    sort(v,v+M),reverse_copy(v,v+M-1,v+M);
    for(i=0;i<2*M-1;h[j++]=v[i++])
        while(j>1&&d(h[j-2],h[j-1],v[i]))
            --j;
    printf("%d\n",--j);
    for(i=0;i<j;++i)
        printf("%.9lf %.9lf\n",h[i].x,h[i].y);
    return 0;
}