iuly

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <math.h>
using namespace std;

template<typename T> struct point {
    T x;
    T y;
    struct point<T> *next, *prev;
};

template <typename T> class LinkedList {
    public:
        struct point<T> *pfirst, *plast;

    void addFirst(T x, T y) {
            struct point<T> *paux;

            paux = new struct point<T>;
            paux->x = x;
            paux->y = y;
            paux->prev = NULL;
            paux->next = pfirst;

            if (pfirst != NULL) pfirst->prev = paux;
            pfirst = paux;

            if (plast==NULL) plast=pfirst;
        }

        void addLast(T x, T y) {
            struct point<T> *paux;

            paux = new struct point<T>;
            paux->x = x;
            paux->y = y;
            paux->prev = plast;
            paux->next = NULL;

            if (plast != NULL) plast->next = paux;
            plast = paux;
            if (pfirst == NULL) pfirst = plast;
        }
    void removeFirst() {
            struct point<T>* paux;

            if (pfirst != NULL) {
                paux = pfirst->next;
                if (pfirst == plast) plast = NULL;
                delete pfirst;
                pfirst = paux;
                if (pfirst != NULL) pfirst->prev = NULL;
            }
            else cout<<"The list is empty"<<endl;
		}

		void removeLast() {
            struct point<T> *paux;

            if (plast != NULL) {
                paux = plast->prev;
                if (pfirst == plast) pfirst = NULL;
                delete plast;
                plast = paux;
                if (plast != NULL) plast->next = NULL;
            }
            else cout<<"The list is empty"<<endl;
        }
    struct point<T>* findFirstOccurrence(T x, T y) {
            struct point<T> *paux;

            paux = pfirst;
            while (paux != NULL) {
                if (paux->x == x && paux->y == y)
                    return paux;
                paux = paux->next;
            }
            return NULL;
        }

        struct point<T>* findLastOccurrence(T x, T y) {
            struct point<T> *paux;

            paux = plast;
            while (paux != NULL) {
               if (paux->x == x && paux->y == y)
                    return paux;
                paux = paux->prev;
            }

            return NULL;
        }

    int isEmpty() {
            return (pfirst == NULL);
        }

    LinkedList() {
        pfirst = plast = NULL;
    }

    void printList()
  {
	struct point<T> *p;

	p = pfirst;
	while (p != NULL)
	{
		printf("%d %d\n", p->x , p->y);
		p = p->next;
	}
  }


   struct point<T> *merge(struct point<T> *first, struct point<T> *second){

        if (!first)
            return second;

        if (!second)
            return first;

        if(sqrt((first->x)^2+(first->y)^2) < sqrt((second->x)^2+(second->y)^2))

        {
            first->next = merge(first->next,second);
            first->next->prev = first;
            first->prev = NULL;
            return first;
        }
        else
        {
            second->next = merge(first,second->next);
            second->next->prev = second;
            second->prev = NULL;
            return second;
        }
    }

    struct point<T> *mergeSort(struct point<T> *head)
    {
        if (!head || !head->next)
            return head;
        struct point<T> *second = split(head);

        // Recur for left and right halves
        head = mergeSort(head);
        second = mergeSort(second);

        // Merge the two sorted halves
        return merge(head,second);
    }

    void sort() {
        pfirst = mergeSort(pfirst);
    }

    struct point<T> *split(struct point<T> *head)
    {
        struct point<T> *fast = head,*slow = head;
        while (fast->next && fast->next->next)
        {
            fast = fast->next->next;
            slow = slow->next;
        }
        struct point<T> *temp = slow->next;
        slow->next = NULL;
        return temp;
    }

};

int main()
{   int n,x,y;
    LinkedList<int> l;
    cout<<"Number of points: ";
    cin>>n;

    for(int i=0; i<n;i++)
    {
        cout<<"For "<<i<<" point enter: "<<endl;
        cout<<"x= ";
        cin>>x;
        cout<<"y= ";
        cin>>y;
        l.addLast(x,y);
    }
    l.printList();
    l.sort();
    cout<< endl;
    cout << "Sorted list: "<< endl;
    l.printList();

    return 0;
}