Cod sursa(job #1679064)

Utilizator roxi22Roxi C. roxi22 Data 7 aprilie 2016 17:41:46
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 3.25 kb
#include <fstream>
#include <cmath>
using namespace std;

ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");

struct puncte{
    double x,y;
    double cosinus;
}x[120001],minim;

puncte stiva[1000];
puncte p1;

void adaugare(int &n,puncte inf[],puncte v){
    //n++;
    inf[n]=v;
    int k=n;
    puncte aux;
    while(k!=1)
        if(inf[k].cosinus<inf[k/2].cosinus||(inf[k].cosinus==inf[k/2].cosinus&&sqrt((inf[k].x-minim.x)*(inf[k].x-minim.x)-(inf[k].y-minim.y)*(inf[k].y-minim.y))>sqrt((inf[k/2].x-minim.x)*(inf[k/2].x-minim.x)-(inf[k/2].y-minim.y)*(inf[k/2].y-minim.y))))
            {aux=inf[k];
            inf[k]=inf[k/2];
            inf[k/2]=aux;
            k/=2;}
        else
            k=1;}

void eliminare(int &n,puncte inf[],puncte &v){
    v=inf[1];
    inf[1]=inf[n];
    n--;
    int k=1;
    while(2*k<=n)
        {int vmax;
        puncte aux;
        if(2*k+1<=n)
            if(inf[2*k].cosinus<inf[2*k+1].cosinus)
                    vmax=2*k;
            else
                    vmax=2*k+1;
        else
            vmax=2*k;
        if(inf[vmax].cosinus<inf[k].cosinus)
                {aux=inf[vmax];
                inf[vmax]=inf[k];
                inf[k]=aux;
                k=vmax;}
        else
            k=n+1;}}

int main()
{
    int n;
    fin>>n;
    for(int i=1;i<=n;i++)
        fin>>x[i].x>>x[i].y;
    minim.y=x[1].y;
    minim.x=x[1].x;
    for(int i=1;i<=n;i++)
        {if(x[i].y<minim.y)
            {minim.y=x[i].y;
            minim.x=x[i].x;}
        if(x[i].y==minim.y)
            if(x[i].x<minim.x)
                minim.x=x[i].x;}
    //fout<<minim.x<<" "<<minim.y<<" ";
    //fout<<"\n";
    for(int i=1;i<=n;i++)
        if(x[i].x==minim.x&&x[i].y==minim.y)
            x[i].cosinus=2;
        else
            {double ip=sqrt((minim.x-x[i].x)*(minim.x-x[i].x)+(minim.y-x[i].y)*(minim.y-x[i].y));
            double cal=x[i].x-minim.x;
            x[i].cosinus=cal/ip;}
    //for(int i=1;i<=n;i++)
        //fout<<x[i].cosinus<<"\n";
    for(int i=1;i<=n;i++)
        adaugare(i,x,x[i]);
    int k=n;
    while(k!=1)
        {puncte v;
        eliminare(k,x,v);
        x[k+1]=v;}
    //fout<<"\n";
    //for(int i=1;i<=n;i++)
       // fout<<x[i].x<<" "<<x[i].y<<"\n";//<<x[i].cosinus<<"\n";
    for(int i=1;i<=3;i++)
        stiva[i]=x[i];
    int p=3;
    for(int i=4;i<=n;i++)
    {
        double d=stiva[p-1].x*stiva[p].y+stiva[p].x*x[i].y+x[i].x*stiva[p-1].y-
           x[i].x*stiva[p].y-stiva[p-1].x*x[i].y-stiva[p].x*stiva[p-1].y;
        if(d<=0)
                stiva[p]=x[i];
        else
            p++,stiva[p]=x[i];
    }
    fout<<p<<"\n";
    for(int i=1;i<=p;i++)
        fout<<stiva[i].x<<" "<<stiva[i].y<<"\n";
    fout<<"\n";
    /*double arietotala=0;
    for(int i=3;i<=p;i++)
        {//fout<<stiva[i].x<<" "<<stiva[i].y<<"\n";
        //fout<<stiva[i-1].x<<" "<<stiva[i-1].y<<"\n\n";
        double d=abs(double(stiva[1].x*stiva[i].y+stiva[1].y*stiva[i-1].x+stiva[i].x*stiva[i-1].y
                            -stiva[i].y*stiva[i-1].x-stiva[i-1].y*stiva[1].x-stiva[1].y*stiva[i].x));
        double arie=1/2.0*d;
        fout<<arie<<"\n";
        arietotala+=arie;}
    fout<<arietotala;*/
    return 0;
}