#include <stdio.h>
#include <stdlib.h>
#include <math.h>

unsigned  k, nrPersImport, nrPersInDrum;
unsigned short id = 0;
double distParcurs, combustibil;

typedef struct Calls
{
    unsigned short x, y, prioritate, id;
    struct Calls *urm;

}nevoiasi;
typedef enum { Very_Low, Low, Medium, High, Very_High } prioritate;
prioritate prio[5];
nevoiasi *persImport[100], *persInDrum[100];

void ADD_Call(nevoiasi *prim) {
    nevoiasi *q, *p;
    id++;
    system("cls");
    printf("Nevoiasul %hu\n", id);
    p = (nevoiasi *)malloc(sizeof(nevoiasi));
    printf("x= "); scanf("%hu", &p->x);
    printf("y= "); scanf("%hu", &p->y);
    printf("prioritate= "); scanf("%hu", &p->prioritate);
    p->urm = NULL;
    p->id = id;
    q = prim;
    while (q->urm != NULL && q->urm->x < p->x)
        q = q->urm;
        while (q->urm != NULL && q->urm->x == p->x && q->urm->y < p->y)
        q = q->urm;

    p->urm = q->urm;
    q->urm = p;
}
void Afisare(nevoiasi *prim) {
    nevoiasi *q;
    q = prim->urm;
    while (q != NULL) {
        printf("\n%d %d\n", q->x, q->y);
        q = q->urm;
    }
}
double Dist(nevoiasi *p, nevoiasi *q) {
    return sqrt(pow(q->x - p->x, 2) + pow(q->y - p->y, 2));
}


double SetPriority(nevoiasi *prim) {
    nevoiasi *q = prim->urm, *p = prim, *t = prim;
    nrPersImport = 0;
    int i;
    double dist = 0;
    for (i = Very_Low; i <= Very_High; i++)
        prio[i] = 0;
    persImport[nrPersImport++] = prim;
    while (q)
    {

        prio[q->prioritate]++;
        if (q->prioritate == Very_High && nrPersImport <= k) {
            if (dist + Dist(p, q) + Dist(prim, q) <= combustibil) {
                dist += Dist(p, q);
                p = q;
                persImport[nrPersImport] = t;
                nrPersImport++;
            }
        }
        t = q;
        q = q->urm;
    }
    return dist + Dist(prim, p);
}
void GrowPriority(nevoiasi *prim) {
    nevoiasi *q = prim->urm;
    while (q)
    {
        if (q->prioritate < Very_High)
            q->prioritate ++;
        q = q->urm;
    }
}

void DeleteCall(nevoiasi *p) {
    nevoiasi *q = p->urm;
    printf(" %hu ", q->id);
    p->urm = p->urm->urm;
    free(q);
}

void PersInDrum() {
    nevoiasi *q, *t;
    nrPersInDrum = 0;
    int i, n = nrPersImport - 1;
    for (i = 0; i < n; i++) {
        q = persImport[i]->urm;
        int a = persImport[i + 1]->urm->x - persImport[i]->urm->x;
        int b = persImport[i + 1]->urm->y - persImport[i]->urm->y;
        if(persImport[i] != persImport[i+1])
        while (q->urm != NULL && q->urm != persImport[i+1]->urm)
        {
            t = q;
            q = q->urm;
            if (b * (q->x - persImport[i]->urm->x) == a * (q->y - persImport[i]->urm->y)) {
                persInDrum[nrPersInDrum] = t;
                nrPersInDrum++;
            }
        }
    }

}
void Sort() {
    int i, ok;
    nevoiasi *aux;
    do {
        ok = 0;
        for (i = nrPersImport - 2; i; i--)
            if (persImport[i]->x > persImport[i + 1]->x || (persImport[i]->x == persImport[i + 1]->x && persImport[i]->y > persImport[i + 1]->y)) {
                aux = persImport[i];
                persImport[i] = persImport[i + 1];
                persImport[i + 1] = aux;
                ok = 1;
            }
    } while (ok);

}

int main() {
    unsigned days = 1, i, nrCalls;
    nevoiasi *prim = (nevoiasi *)malloc(sizeof(nevoiasi));
    prim->x = 0;
    prim->y = 0;
    prim->prioritate = 0;
    prim->urm = NULL;
    printf("Numarul de pachete ce pot fi livrate: "); scanf("%u", &k);
    printf("Numarul de apeluri: "); scanf("%u", &nrCalls);
    for (i = 1; i <= nrCalls; i++)
        ADD_Call(prim);

    do {

        combustibil += 10000;
        distParcurs = SetPriority(prim);

        if (prio[Very_High]) {
            if (k - prio[Very_High])
                PersInDrum();
            combustibil -= distParcurs;
            for (i = nrPersInDrum + nrPersImport - k -1; i < nrPersInDrum; i++)
                persImport[nrPersImport++] = persInDrum[i];
            Sort();
            printf("\nRezumat sfarsit de zi %u:", days);
            printf("\nAu fost sterse apelurile: ");
            for (i = nrPersImport - 1; i; i--)
                DeleteCall(persImport[i]);
            printf("\nCombustibil ramas %f L\n", combustibil);
            printf("Au fost livrate %u pachete\n", nrPersImport - 1);

        }
        else
            printf("test\n");
        GrowPriority(prim);
        days++;
        nrCalls = nrCalls - nrPersImport + 1;
    } while (prim->urm);
    system("pause");
    return 0;
}