Задача D

Задача D. Порожній прямокутник

Ім’я вхідного файлу: іnput.txt

Ім’я вхідного файлу: output.txt

Ліміт часу: 2с.

  Задано N різних точок на площині (2≤N≤1000). Виберемо будь-які дві точок з даної множини з координатами (x1, y1) і (x2, y2). Для цієї пари точок можна побудувати прямокутник зі сторонами, паралельними осям координат, так що обрані точки будуть перебувати в протилежних кутах прямокутника. Прямокутник, побудований таким чином, назвемо порожнім, якщо всередині нього і на його границі немає інших заданих точок. Вам потрібно визначити, скільки різних порожніх прямокутників можна побудувати із заданого множини точок.

Вхідні дані

               Вхідні дані складаються з декількох рядків. Перший рядок файлу містить величину N(кількість точок). У кожному наступному рядкові через пропуск задаються координати X і Y однієї точки з множини цілих чисел, що не перевищують по модулю 1000000 (в 50% тестів координати не перевищують по модулю 10000).

Вихідні дані

Вихідні дані містять єдиний рядок зі знайденим числом порожніх прямокутників

Приклад

іnput.txt	output.txt
5 -1 4 1 4 1 1 2 1 -2 2	2

Ідея.

Перебрати всі пари точок, вибравши ті, що утворюють прямокутник. Для кожного прямокутника перевірити чи жодна з заданих точок в нього не потрапляє.

Для прискорення роботи програми точки можна відсортувати за координатою х, наприклад. А під час перебору точок, перевіряючи чи потрапляють в прямокутник, можна розглядати лише ті точки, як знаходяться правіше від початку прямокутника.

Особливості реалізації:

1. Дані про окрему точку зручно подати у вигляді структури.

2. Сортування цілих чисел можна виконувати функцією sort(points.begin(), points.end()) з бібліотеки std, яка використовує функцію порівняння цілих чисел за замовчуванням. Однак, для власноруч створеної структури потрібно описати функцію порівняння:

bool comparePoint(Point p1, Point p2){ return p1.x<p2.x; }

Така функція буде впорядковувати точки за зростанням координати Х.

3. Повний перебір всіх пар точок здійснюється вкладеним подвійним циклом for:

for (int i = 0; i<n-1; ++i)

             for (int j = i+1; j<n; ++j)

             {

                    …

}

Щоб уникнути повторного перегляду точок, зовнішній цикл (по і) перебирає всі точки від першої, до передостанньої, а внутрішній цикл (по j) – від поточної (і+1) до останньої. Оскільки точки перед цим були відсортовані, то перегляд відбувається справа на ліво  вздовж координатної прямої Х.

4. Пара точок утворює прямокутник, якщо точки лежать в протилежних вершинах 9тут можуть бути різні варіанти розташування вершин). Функція  isRect дозволяє визначити чи утворюють дві точки прямокутник, згідно умови задачі: p1.x != p2.x && p1.y != p2.y.

5. Оскільки точки відсортовані, то перевіряти їх належність прямокутнику можна починаючи з наступної за поточною точкою, яка утворює ліву крайню (верхню або нижню) вершину прямокутника:

for (int k = i+1; k < n; ++k)…

6. Перевірити, чи «точка належить прямокутнику» означає. що потрібно перевірити чи Х цієї точки лежить між Х-ами лівої та правої вершини, і так само чи Y точки лежить між Y-ами верхньої та нижньої вершин. Оскільки, можуть бути різні розташування точок-вершин прямокутника, то (навіть без сортування) перевірити належнітсь іншої точки до прямокутника дозволяє функція isPointInRect:

bool qx = p1.x <= p.x && p.x <= p2.x || p2.x <= p.x && p.x <= p1.x;

       bool qy = p1.y <= p.y && p.y <= p2.y || p2.y <= p.y && p.y <= p1.y;

       return qx && qy;

7. Алгоритм визначення належності точки до прямокутника:

припустимо, що прямокутник порожній;

для всіх точок, які лежать правіше від початку прямокутника

            якщо точка співпадає з однією з вершин, то її пропустити

             якщо точка належить прямокутнику, тоді прямокутник непорожній і перебір-перевірку точок зупинити.

 Якщо прямокутник порожній, тоді збільшити лічильник таких прямокутників на 1

Реалізація алгоритму:
bool isempty = true;

                           
for (int k = i+1; k < n; ++k) {                                  

  if (i == k || j == k) continue;                                  

  if (isPointInRect(points[i], points[j], points[k])) {                                       

           isempty = false;

           break;

  }

}

if (isempty)

      cnt++;

#include <stdio.h>

#include <vector>

#include <algorithm>

using namespace std;

struct Point

{

       int x, y;

};

bool comparePoint(Point p1, Point p2){ return p1.x<p2.x; }

int n;

vector<Point> points;

bool isRect(Point p1, Point p2);

bool isPointInRect(Point p1, Point p2, Point p);

int main()

{

       freopen("input.txt", "r", stdin);

       freopen("output.txt", "w", stdout);

       int n;

       scanf("%d", &n);

       points.assign(n, Point());

       for(int i=0; i<n; ++i)

       {

             int x, y;

             scanf("%d%d", &x, &y);

             points[i].x = x; points[i].y = y;

       }

       sort(points.begin(), points.end(), comparePoint);

       int cnt = 0;

       for (int i = 0; i<n-1; ++i)

             for (int j = i+1; j<n; ++j)

             {

                    if (isRect(points[i], points[j]))

                    {

                           bool isempty = true;

                           for (int k = i+1; k < n; ++k)

                           {

                                  if (i == k || j == k) continue;

                                  if (isPointInRect(points[i], points[j], points[k])) {

                                        isempty = false;

                                        break;

                                  }

                           }

                           if (isempty)

                                  cnt++;

                    }

             }

             printf("%d\n", cnt);

             return 0;

}

bool isRect(Point p1, Point p2)

{

       return p1.x != p2.x && p1.y != p2.y;

}

bool isPointInRect(Point p1, Point p2, Point p)

{

       bool qx = p1.x <= p.x && p.x <= p2.x || p2.x <= p.x && p.x <= p1.x;

       bool qy = p1.y <= p.y && p.y <= p2.y || p2.y <= p.y && p.y <= p1.y;

       return qx && qy;

}