/ 알고리즘

두현의교차유무

알고리즘 두 현의 교차
https://4am.kr/-eb-91-90-ed-98-84-ec-9d-98-ea-b5-90-ec-b0-a8-ec-9c-a0-eb-ac-b4/

프로그램 명: cross(open)

제한시간: 1 초
원을 가로 지르는 선분을 현이라 한다.

chord1

원에는 1 부터 100 까지 일정한 간격으로 점이 부여되어 있다.

chord2

두 개의 현이 주어질 때 이 현이 교차하는지 아닌지를 판단하는 프로그램을 작성하시오.

아래 그림은 두 현이 교차하는 경우의 예이다.

chord3

입력 형식

첫 줄에는 한 현의 정보가 다음 줄에는 다른 한 현의 정보가 입력된다. 숫자는 1 이상 100 이하인 서로 다른 자연수이다.

출력 형식

두 현이 교차하면 cross ,아니면 not cross 를 출력한다.

입출력 예

입력 20 80 85 40 출력 cross

#include <iostream>
using namespace std;
int main()
{
    int a1, a2, b1, b2, temp, m = 0, m2 = 0;
    scanf("%d %d", &a1, &a2);
    scanf("%d %d", &b1, &b2);
    //현의 성분 4개를 각 현 기준으로 크기순 정렬하여 자리바꿈한다.
    if (a1 < a2) {
        temp = a1;
        a1 = a2;
        a2 = temp;
    }
    if (b1 < b2) {
        temp = b1;
        b1 = b2;
        b2 = temp;
    }
    //두번째 현 기준으로 크로스인지 아닌지 판별한다.
    // b1이 현 a의 가장 큰 성분인 a1과 100 사이의 영역에 들어가면서
    // b2가 동시에 들어가지 않는지 확인한다.
    if ((b1 > a1 && b1 <= 100) && !(b2 > a1 && b2 <= 100))
        m = 1;
    // b2가 현 a의 가장 작은 성분인 a2와 0 사이의 영역에 들어가면서
    // b1이 동시에 들어가지 않는지 확인한다.
    if ((b2 < a2 && 0 <= b2) && !(b1 < a2 && 0 <= b1))
        m = 1;
    // b1과 b2가 이루는 현이 a1과 b2의 영역 바깥에 있지는 않은지 확인한다. if (m == 1 && b1 > a1 && b2 < a2) m = 0;
    if (m == 1)
        cout << "cross";
    else
        cout << "not cross";
}