Cod sursa(job #1922700)

Utilizator cosminmaneaCosmin Manea cosminmanea Data 10 martie 2017 18:30:43
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.13 kb
#include <cstdio>
#include <cmath>
#include <algorithm>

struct pct {double x,y;} P[120010];
int n,vfsup=-1,vfinf=-1;

pct stsup[120010],stinf[120010];

bool comppct(pct x,pct y)
{
    return x.x<y.x||x.x==y.x&&x.y<y.y;
}

int parte(pct a,pct b,pct c)
{
    double det=a.x*b.y+b.x*c.y+c.x*a.y-c.x*b.y-a.x*c.y-a.y*b.x;
    if(det<0)return -1;
    return 1;
}

int main()
{
    FILE *f=fopen("infasuratoare.in","r");
    fscanf(f,"%d",&n);
    int i;
    for(i=1;i<=n;i++)
        fscanf(f,"%lf%lf",&P[i].x,&P[i].y);
    std::sort(P+1,P+n+1,comppct);
    stsup[++vfsup]=P[1];
    stinf[++vfinf]=P[1];
    for(i=2;i<=n-1;i++)
        if(parte(P[1],P[i],P[n])==-1)
        {//partea superioara
            if(vfsup==0)stsup[++vfsup]=P[i];
            else
            {//tre sa vad cum stau cu stsup[vfsup-1], stsup[vfsup] shi P[i]
                while(vfsup>0 && parte(stsup[vfsup-1],stsup[vfsup],P[i])==1)vfsup--;
                stsup[++vfsup]=P[i];
            }
        }
        else
        {//partea inferioara
            if(vfinf==0)stinf[++vfinf]=P[i];
            else
            {//tre sa vad cum stau cu stinf[vfinf-1], stinf[vfinf] shi P[i]
                while(vfinf>0 && parte(stinf[vfinf-1],stinf[vfinf],P[i])==-1)vfinf--;
                stinf[++vfinf]=P[i];
            }
        }
    //repet pentru ambele stive cu ultimul punct (fara a mai verifica partea)
    if(vfsup==0)stsup[++vfsup]=P[n];
    else
    {//tre sa vad cum stau cu stsup[vfsup-1], stsup[vfsup] shi P[n]
        while(vfsup>0 && parte(stsup[vfsup-1],stsup[vfsup],P[n])==1)vfsup--;
        stsup[++vfsup]=P[n];
    }
    if(vfinf==0)stinf[++vfinf]=P[n];
    else
    {//tre sa vad cum stau cu stinf[vfinf-1], stinf[vfinf] shi P[n]
        while(vfinf>0 && parte(stinf[vfinf-1],stinf[vfinf],P[n])==-1)vfinf--;
        stinf[++vfinf]=P[n];
    }
    FILE *g=fopen("infasuratoare.out","w");
    fprintf(g,"%d\n",vfsup+vfinf);
    for(i=vfsup;i>=0;i--)
        fprintf(g,"%13.12lf %13.12lf\n",stsup[i].x,stsup[i].y);
    for(i=1;i<vfinf;i++)
        fprintf(g,"%13.12lf %13.12lf\n",stinf[i].x,stinf[i].y);
    return 0;
}