main.cpp

#include <iostream>
#include <cstring>
#include "deque.cpp"
using namespace std;

bool is_polyndrome(string str)
{
	Deque<char> mdeq;
	for (int i = 0; i < str.length(); i++)
	{
		if (str[i] != ' ')
		{
			mdeq.pushback(tolower(str[i]));
		}
	}

	while (not(mdeq.isEmpty()))
	{
		if (mdeq.front() != mdeq.last())
		{
			return false;
		}
		mdeq.popfront();
		mdeq.popback();
	}
	return true;
}


struct Point {
    int x, y;
};

// Îïðåäåëÿåò, ñ êàêîé ñòîðîíû îò âåêòîðà AB íàõîäèòñÿ òî÷êà C
// Åñëè > 0 — C ñëåâà, åñëè < 0 — C ñïðàâà, åñëè = 0 — òî÷êè êîëëèíåàðíû
int orientation(Point A, Point B, Point C) {
    return (B.x - A.x) * (C.y - B.y) - (B.y - A.y) * (C.x - B.x);
}

// Ôóíêöèÿ äëÿ ïîèñêà ñàìîé ëåâîé (èëè ñàìîé íèæíåé ïðè ðàâíûõ x) òî÷êè
// Ýòà òî÷êà ãàðàíòèðîâàííî âõîäèò â âûïóêëóþ îáîëî÷êó
Point findStart(Point* points, int n) {
    Point start = points[0]; // Èçíà÷àëüíî ïðèíèìàåì ïåðâóþ òî÷êó çà ñàìóþ ëåâóþ
    for (int i = 1; i < n; i++) {
        // Åñëè âñòðå÷àåì òî÷êó ñ ìåíüøåé x-êîîðäèíàòîé, îáíîâëÿåì start
        // Åñëè x-êîîðäèíàòû ñîâïàäàþò, âûáèðàåì òî÷êó ñ ìåíüøåé y-êîîðäèíàòîé
        if (points[i].x < start.x || (points[i].x == start.x && points[i].y < start.y)) {
            start = points[i];
        }
    }
    return start;
}

// Ñîðòèðîâêà ïóçûðüêîì òî÷åê ïî ïîëÿðíîìó óãëó îòíîñèòåëüíî ñòàðòîâîé òî÷êè
// ×åì áîëüøå ëåâèçíà îòíîñèòåëüíî ñòàðòîâîé òî÷êè, òåì ðàíüøå òî÷êà èäåò â ñïèñêå
void sortPoints(Point* points, int n, Point start) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            // Åñëè òî÷êà points[j+1] íàõîäèòñÿ ëåâåå òî÷êè points[j] îòíîñèòåëüíî start, ìåíÿåì èõ ìåñòàìè
            if (orientation(start, points[j], points[j + 1]) < 0) {
                Point temp = points[j];
                points[j] = points[j + 1];
                points[j + 1] = temp;
            }
        }
    }
}
// Ðåàëèçàöèÿ àëãîðèòìà Ãðýõåìà
void grahamScan(Point* points, int n, Deque<Point>& hull) {
    if (n < 3) return; // Ìèíèìàëüíîå êîëè÷åñòâî òî÷åê äëÿ âûïóêëîé îáîëî÷êè — 3

    Point start = findStart(points, n); // Íàõîäèì ñòàðòîâóþ òî÷êó
    sortPoints(points, n, start); // Ñîðòèðóåì îñòàâøèåñÿ òî÷êè

    hull.pushback(points[0]); // Äîáàâëÿåì ïåðâóþ òî÷êó â îáîëî÷êó
    hull.pushback(points[1]); // Äîáàâëÿåì âòîðóþ òî÷êó â îáîëî÷êó

    for (int i = 2; i < n; i++) {
        while (hull.getSize() > 1) {
            Point second = hull.last(); // Âòîðàÿ âåðøèíà ñòåêà (ïîñëåäíÿÿ äîáàâëåííàÿ)
            hull.popback(); // Óáèðàåì å¸ âðåìåííî

            if (hull.isEmpty()) { // Ïðîâåðêà, ÷òîáû íå âûçûâàòü last() ó ïóñòîãî deque
                hull.pushback(second);
                break;
            }

            Point first = hull.last(); // Ïåðâàÿ âåðøèíà ñòåêà (ïðåäïîñëåäíÿÿ äîáàâëåííàÿ)

            if (orientation(first, second, points[i]) > 0) { // Ïðîâåðÿåì íàïðàâëåíèå ïîâîðîòà
                hull.pushback(second); // Åñëè ïîâîðîò ëåâûé, âîçâðàùàåì âòîðóþ òî÷êó
                break;
            }
        }
        hull.pushback(points[i]); // Äîáàâëÿåì íîâóþ òî÷êó â îáîëî÷êó
    }
}

// Òåñòîâûé ïðèìåð
int main() {
  
  /*
    Point points[] = { {0, 0}, {0, 1}, {2, 2}, {2, 0}, {2, 4}, {3, 3}, {0, 3}, {1,1} };
    int n = sizeof(points) / sizeof(points[0]);

    Deque<Point> convexHull;
    grahamScan(points, n, convexHull); // Âû÷èñëÿåì âûïóêëóþ îáîëî÷êó

    std::cout << "Convex Hull:\n";
    while (!convexHull.isEmpty()) {
        Point p = convexHull.front();
        convexHull.popfront();
        std::cout << "(" << p.x << ", " << p.y << ")\n"; // Âûâîä òî÷åê îáîëî÷êè
    }
    return 0;
    */
    
    
    //------------------------------------------------------------
   
  
    
    string str;
    cout << "Input str: ";
    cin >> str;
    if (is_polyndrome(str))
    {
        cout << "is polyndrome";
    }
    else
    {
        cout << "is not polyndrome";
    }
    
   
}