아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

초

면접 대비

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

요약
원 안에 놓인 n개의 초와 케이크를 자르는 m개의 직선이 주어질 때, 두 개 이상의 초를 포함하는 조각이 있는지 판별한다.
난이도

보통10점 중 5점

유형
기하, 해시맵, 정렬, 구현
정답자
아직 제출이 없습니다

문제

미샤가 nn살이 되었다. 생일을 맞아 구운 케이크는 원점을 중심으로 하는 반지름 rr의 원 모양이다. 케이크 위에는 nn개의 초가 꽂혀 있다. 미샤의 어머니는 mm번의 직선 절단을 해서 케이크를 여러 조각으로 나누었다. 손님들은 각자 그중 한 조각을 가져갔다.

미샤는 손님 중 누군가가 초를 두 개 이상 받았는지 알고 싶어 한다. 이를 알아내도록 도와주자.

입력

입력 파일의 첫째 줄에는 정수 nn, mm, rr이 주어진다 (1≤n≤100001\le n\le 10000, 0≤m≤10000\le m\le 1000, 1≤r≤20001\le r\le 2000).

다음 nn개의 줄에는 초가 놓인 점의 좌표인 정수 쌍 x_i,y_ix\_i, y\_i가 주어진다. 이 점들은 원 안에 있고 초의 크기는 무시할 수 있다. 두 초가 같은 위치에 있는 경우는 없다.

마지막 mm개의 줄에는 절단에 대한 설명이 주어진다. 각 줄은 정수 세 개 a_i,b_i,c_ia\_i, b\_i, c\_i로 이루어진다. 이 세 정수는 a_ix+b_iy+c_i=0a\_i x + b\_i y + c\_i = 0으로 정의되는 절단을 나타낸다. 어떤 절단도 초를 지나지 않는다. 두 절단이 같은 경우는 없다. a_i,b_i,c_ia\_i, b\_i, c\_i의 절댓값은 1000010000을 넘지 않는다.

출력

손님 중 한 명이 초를 두 개 이상 받았다면 출력 파일에 <<YES>>를 출력하고, 그렇지 않으면 <<NO>>를 출력한다.

예제3

  1. 예제 1

    입력
    3 2 3
    2 2
    1 -1
    -2 0
    2 -1 0
    0 1 -1
    
    예상 출력
    NO
    
  2. 예제 2

    입력
    3 2 3
    2 2
    1 -1
    -2 0
    1 1 -1
    0 1 -1
    
    예상 출력
    YES
    
  3. 예제 3

    입력
    1 0 100
    0 0
    
    예상 출력
    NO