Районная олимпиада по информатике. 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()