Cod sursa(job #890865)

Utilizator gabriel93Robu Gabriel gabriel93 Data 25 februarie 2013 12:30:08
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.65 kb
#include<stdio.h>
#include<math.h>
#include<stack>
#define Nmax 120002
using namespace std;
int n;
int viz[Nmax];
float x[Nmax],y[Nmax];
float pi=3.141592;
stack<int> st;

void citire()
{
    int i;
    scanf("%d",&n);
    for(i=1;i<=n;++i)
        scanf("%f %f",&x[i],&y[i]);
}

void rezolv()
{
    int i,start,poz,next,ok;
    float unghi,last,maxim;
    start=1;
    for(i=2;i<=n;++i)
        if(x[start] > x[i])
            start=i;
        else
            if(x[start]==y[start] && y[start] > y[i])
                start=i;
    poz=start;
    next=0;
    ok=1;
    last=0;
    while(ok==1 || poz!=start)
    {
        ok=0;
        st.push(poz);
        next=poz;
        maxim=-1;
        for(i=1;i<=n;++i)
            if(viz[i]==0 && i!=poz)
            {
                unghi=atan2(x[i]-x[poz],y[i]-y[poz]);
                if(unghi<0)
                    unghi+=2*pi;
                unghi-=last;
                if(unghi<0)
                    unghi+=2*pi;
                if(unghi > maxim)
                {
                    maxim=unghi;
                    next=i;
                }
            }
        last=atan2(x[next]-x[poz],y[next]-y[poz]);
        if(last<0)
            last+=2*pi;
        poz=next;
        viz[poz]=1;
    }
}

void scrie()
{
    printf("%d\n",st.size());
    while(!st.empty())
    {
        printf("%f %f\n",x[st.top()],y[st.top()]);
        st.pop();
    }
}

int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    citire();
    rezolv();
    scrie();
    fclose(stdin);
    fclose(stdout);
    return 0;
}