Cod sursa(job #1041943)

Utilizator tavi.belu1994FMI Belu Andrei Octavian tavi.belu1994 Data 26 noiembrie 2013 13:27:48
Problema Infasuratoare convexa Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.8 kb
#include <iostream>
#include <cstdio>
#include <cmath>
#define _USE_MATH_DEFINES
#define MAXN 120000
FILE *f,*g;
using namespace std;

typedef struct point{
    double x,y;
};

point V[MAXN];
int N,k;
int poz;
int VECT[MAXN];
int VIZ[MAXN];

void read()
{
    f=fopen("infasuratoare.in","r");
    fscanf(f,"%ld\n",&N);
    V[0].x = V[0].y = 1000000000;
    poz = 0;
    for(int i=1 ; i<=N ; i++)
    {
        fscanf(f,"%lf%lf\n",&V[i].x,&V[i].y);
        if(V[i].x < V[poz].x)
        {
            poz = i;
        }
        else
        {
            if(V[i].x == V[poz].x && V[i].y < V[poz].y)
            {
                poz = i;
            }
        }
    }
    fclose(f);
}



int main()
{
    read();
    int i;
    int punct_initial = poz;
    int curent = punct_initial;
    int muta = 1;
    double last = 0;
    while(muta || punct_initial!=curent)
    {
        muta = 0;
        VECT[++k]=curent;
        double ma = 10000;
        poz = curent;
        for(i=1;i<=N;i++)
        {
            if(VIZ[i] || i==curent)
            {
                continue;
            }
            double unghi = atan2((V[i].x - V[curent].x),(V[i].y - V[curent].y));
            if(unghi < 0)
            {
                unghi += 2 * M_PI;
            }
            if(ma > unghi)
            {
                ma = unghi;
                poz = i;
            }
        }
        last = atan2(-(V[curent].x - V[poz].x),-(V[curent].y - V[poz].y));
        if(last < 0)
            last += 2 * M_PI;
        curent = poz;
        VIZ[curent] = 1;
    }
    k--;
    g=fopen("infasuratoare.out","w");
    fprintf(g,"%d\n",k);
    for(i=k ; i>=1 ; i--)
    {
        fprintf(g,"%lf %lf\n",V[VECT[i]].x,V[VECT[i]].y);
    }
    fclose(g);
    return 0;
}