20206번 푸앙이가 길을 건너간 이유

문제 출처: https://www.acmicpc.net/problem/20206

그냥 우리학교 대회문제라 오기로 풀어봄...

사고과정

위험지역을 지나냐? 안지나냐? = 결론

좌표계 관점.
1.기울기가 +냐 -냐
기울기가 +라면 그래프 기준 좌측 값들이 +, 기울기가 -라면 그래프 기준 우측 값들이 +
차이가 있음.
2. 그래프가 위험지역을 지난다 == 그래프가 직사각형을 관통한다.
그래프가 직사각형을 관통한다의 여집합 == 그래프가 직사각형을 관통하지 않는다.
그래프가 직사각형을 관통하지 않는다. == 그래프가 위험지역을 지나지 않는다.

그래프가 직사각형을 관통한다 == 직사각형의 네 꼭짓점이 그래프로 인해 두 부분으로 나뉜다
그래프가 직사각형을 관통하지 않는다. == 직사각형의 네 꼭짓점이 그래프로 인해 두 부분으로 나뉘지 않는다 == 네 꼭짓점이 한 부분에 모두 있다. BY 1번에 의해 그렇다면 모든 값들을 대입했을 때 부호가 동일하거나 0이 존재한다.

쓸모없어 보이던 1번의 생각이 2번과의 연관성이 발생하면서 문제 해결.

import sys

A,B,C = list(map(int,sys.stdin.readline().rstrip("\n").split()))
x1,x2,y1,y2 = list(map(int,sys.stdin.readline().rstrip("\n").split()))
X = [x1,x2]
Y = [y1,y2]
def puang(sign):
    for x in X : #네 좌표를 모두 기입
        for y in Y :
            r = A*x+B*y+C
            if r==0: #한 좌표랑 접점. 무조건 ok
                print("Lucky")
                return
            if sign==0 and r>0 :
                sign=1
            elif sign==0 and r<0 :
                sign=-1
            if r*sign<0 :
                print("Poor")
                return
    print("Lucky")

puang(0)      

이분법적인 논리 적용! "역"으로 생각해보면 훨씬 쉽게 접근할 수도 있다. 관통하느냐 관통하지 않느냐.