Can You Reach There?

시간 제한2초메모리 제한2048 MB

요약
각 질의에서 두 표시점과 현재 위치로 만든 선분 위의 점으로 이동할 수 있을 때, 한 점에서 다른 점에 도달할 수 있는지 판정한다.
난이도

어려움10점 중 8점

유형
기하, 수학, 유니온 파인드
정답자
아직 제출이 없습니다

문제

You are given nn distinct marked points on a 2D plane, numbered from 11 to nn. Marked point ii has coordinates (x_i,y_i)(x\_i , y\_i).

In this problem, you are given qq scenarios, numbered from 11 to qq. In each scenario kk, four integers a_ka\_k, b_kb\_k, c_kc\_k, and d_kd\_k are given, indicating that you initially stand at (a_k,b_k)(a\_k, b\_k) and aim to reach (c_k,d_k)(c\_k, d\_k) by repeating the steps described below any number of times.

In a single step, you choose two marked points PP and QQ, which may be identical. Let SS denote the point where you are currently standing, and define a point TT by

PT→=SQ→\overrightarrow{PT}=\overrightarrow{SQ}.

In other words, TT is chosen so that the vector from PP to TT has the same direction and length as the vector from SS to QQ. You may then move to any point on the segment STST, including the point TT itself, and you will stand at that new point.

For each scenario, determine whether the objective can be achieved using the described steps. Note that all scenarios are independent of each other.

입력

The first line of input contains two integers nn and qq (1≤n≤100,0001 ≤ n ≤ 100\\, 000, 1≤q≤100,0001 ≤ q ≤ 100\\, 000). The ii-th of the next nn lines contains two integers x_ix\_i and y_iy\_i (0≤x_i,y_i≤1090 ≤ x\_i , y\_i ≤ 10^9). The input guarantees that no two marked points have the same coordinates.

The next qq lines represent the scenarios. The kk-th of these lines contains four integers a_ka\_k, b_kb\_k, c_kc\_k, and d_kd\_k (0≤a_k,b_k,c_k,d_k≤1090 ≤ a\_k, b\_k, c\_k, d\_k ≤ 10^9; (a_k,b_k)≠(c_k,d_k)(a\_k, b\_k) \ne (c\_k, d\_k)).

출력

Output qq lines. The kk-th line should contain yes if the objective of scenario kk is achievable, or no otherwise.

예제1

  1. 예제 1

    입력
    2 4
    10 0
    0 10
    3 4 6 5
    4 0 7 0
    4 0 16 0
    123 456 789 0
    
    예상 출력
    yes
    yes
    yes
    no