Районная олимпиада по информатике. 2008-2009 учебный год.

Задача A. Окружность

Ограничение по времени:

2 seconds

Ограничение по памяти:

64 megabytes

На окружности на равном расстоянии друг от друга отмечены $N$ точек, пронумерованных против часовой стрелки целыми числами от $1$ до $N$. Вам даны несколько пар хорд этой окружности, концами которых являются данные точки. Для каждой пары хорд определите, пересекаются ли они (касание необходимо считать пересечением).

Формат входного файла

На первой строке входного файла расположены два целых числа: $N$ и $K$ ($1 <= N <= 10^9$, $1 <= K <= 100$). На следующих K строках расположены по 4 целых числа: $A_1$, $B_1$, $A_2$, $B_2$ – номера концов первой хорды ($A_1$, $B_1$) и второй хорды ($A_2$, $B_2$). Числа в строках разделены пробелами.

Формат выходного файла

Для каждой пары хорд из входного файла выведите одну строку, содержащую YES, если диагонали пересекаются и NO, если они не пересекаются.

Примеры:

Вход

4 3
1 3 2 4
1 2 3 4
1 2 3 2

Ответ

YES
NO
YES

Комментарий/решение

показать/скрыть код

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n,k;
    cin >> n >> k;
    for (int i=0; i<k; i++) {
        int a1,b1,a2,b2;
        cin >> a1 >> b1 >> a2 >> b2;
        if (a1>b1) swap(a1,b1);
        if (a2>b2) swap(a2,b2);

        if (a1==a2 || a1==b2 || b1==a2 || b1==b2) cout << "YES\n";
        else if (a1==b1 || a2==b2) cout << "NO\n";
        else if (b2<a1) cout << "NO\n";
        else if (a2>b1) cout << "NO\n";
        else if (a1<a2 && b2<b1) cout << "NO\n";
        else if (a2<a1 && b2>b1) cout << "NO\n";
        else cout << "YES\n";
    }
}

def check_intersection(a1, b1, a2, b2):

# Упорядочим точки на каждой хорде

if a1 > b1:

a1, b1 = b1, a1

if a2 > b2:

a2, b2 = b2, a2

# Проверка пересечения или касания

if (a1 == a2 or a1 == b2 or b1 == a2 or b1 == b2 or

a1 == b1 or a2 == b2):

return "YES"

elif b2 < a1 or a2 > b1 or (a1 < a2 and b2 < b1) or (a2 < a1 and b2 > b1):

return "NO"

else:

return "YES"

def main():

# Ввод количества точек и количества пар хорд

n, k = map(int, input("Введите количество точек и количество пар хорд (n k): ").split())

results = []

# Ввод каждой пары хорд и проверка пересечения

for _ in range(k):

a1, b1, a2, b2 = map(int, input("Введите концы хорд (a1 b1 a2 b2): ").split())

# Проверяем пересечение

result = check_intersection(a1, b1, a2, b2)

results.append(result)

# Вывод результатов

print("\n".join(results))

if __name__ == "__main__":

main()