Cod sursa(job #1838190)

Utilizator lorena1999Marginean Lorena lorena1999 Data 31 decembrie 2016 13:26:44
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.08 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");

struct pct{

    int x, y;

}v[10000];

int n;

void citire()
    {
        f>>n;
        for(int i=1; i<=n; i++)
            f>>v[i].x>>v[i].y;
    }

void afisare()
    {
        for(int i=1;i<=n; i++)
            cout<<v[i].x<<" "<<v[i].y<<endl;
    }

void sortare_y()
    {
        for(int i=1; i<n; i++)
            for(int j=i+1; j<=n; j++)
                if(v[i].y<v[j].y || (v[i].y==v[j].y && v[i].x<v[j].x))
                    swap(v[i], v[j]);
    }

int c, k, r=1;
pct stiv[10000];

bool verif_pct_stiv(pct punct, int rr)
    {
        for(int i=1; i<=rr; i++)
            if(stiv[i].x==punct.x && punct.y==stiv[i].y)
                return true;
        return false;
    }

void bk( pct fix, int m)
    {
        if(m==n-1)
            return;
        for(int i=m+1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
            {
                if(((v[i].y-fix.y)*(v[j].x-fix.x)-(v[i].x-fix.x)*(v[j].y-fix.y))>0)
                    c++;
                else if(((v[i].y-fix.y)*(v[j].x-fix.x)-(v[i].x-fix.x)*(v[j].y-fix.y))<0)
                    k++;
            }
            if(v[i].x==0 && v[i].y==0)
            {
                if(verif_pct_stiv(v[i], r-1)==false)
                {stiv[r]=v[i];
                r++;}
            }
            if(k==0 && c!=0 || c==0 && k!=0)
            {
                if(verif_pct_stiv(v[i], r)==false)
                    {stiv[r]=v[i];
                    r++;}
                c=0;
                k=0;
                bk(v[i], i);
            }
            else {
                k=0;
                c=0;
            }
        }
    }
int main()
    {
        citire();
        sortare_y();
        stiv[r]=v[1];
        r++;
        bk(v[1], 1);
        r--;
        for(int i=1; i<=r/2+1; i++)
            g<<stiv[i].x<<" "<<stiv[i].y<<endl;
        for(int j=r; j>r/2+1; j--)
            g<<stiv[j].x<<" "<<stiv[j].y<<endl;
    }