Cod sursa(job #2757823)

Utilizator cezarinfoTulceanu Cezar cezarinfo Data 6 iunie 2021 18:05:37
Problema Infasuratoare convexa Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include<cstdio>
#include<algorithm>
#include<stack>
using namespace std;
FILE*in=fopen("infasuratoare.in","r");
FILE*out=fopen("infasuratoare.out","w");
int n,i,it,itt;
const int cx=-1000000009;
const int cy=-1000000009;
struct pct
{
    double x,y;
};
pct p[120003],s[120003],ss[120003];
bool sor(pct a,pct b)
{
    return (long long)(b.y-cy)*(a.x-cx)>(long long)(a.y-cy)*(b.x-cx);
}
int main()
{
    fscanf(in,"%d",&n);
    for(i=1;i<=n;i++)
    {
        fscanf(in,"%lf %lf",&p[i].x,&p[i].y);
    }
    sort(p+1,p+n+1,sor);
    s[1]=p[1];
    it=1;
    for(i=2;i<=n;i++)
    {
        while(it>=2&&(s[it].y-s[it-1].y)*(p[i].x-s[it].x)>=(p[i].y-s[it].y)*(s[it].x-s[it-1].x))
        {
            it--;
        }
        it++;
        s[it]=p[i];
    }
    ss[1]=p[n];
    itt=1;
    for(i=n-1;i>=1;i--)
    {
        while(itt>=2&&(ss[itt].y-ss[itt-1].y)*(p[i].x-ss[itt].x)>=(p[i].y-ss[itt].y)*(ss[itt].x-ss[itt-1].x))
        {
            itt--;
        }
        itt++;
        ss[itt]=p[i];
    }
    fprintf(out,"%d\n",it+itt-2);
    for(i=1;i<=it;i++)
    {
        fprintf(out,"%.12f %.12f\n",s[i].x,s[i].y);
    }
    for(i=2;i<itt;i++)
    {
        fprintf(out,"%.12f %.12f\n",ss[i].x,ss[i].y);
    }
}