만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

선형 회귀는 너무 쉬워 1

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

요약
점 n개와 y절편 b가 주어질 때, 각 점의 (a x_i + b - y_i) 합을 0에 가장 가깝게 만드는 기울기 a를 구합니다. 가능한 값이 여러 개이면 EZPZ를 출력합니다.
난이도

쉬움10점 중 2점

유형
수학, 구현
정답자
아직 제출이 없습니다

문제

유림이는 선형 회귀에 자신이 있다. 그래서 MatKor 동아리에서 선형 회귀 수업을 할 때 집중하지 않았다. 당시 강사였던 동우는 이를 못마땅하게 여겨 유림이에게 더 어려운 문제를 냈다. 일반적인 선형 회귀는 데이터 (x1,y1),…,(xn,yn)(x_1, y_1), \dots, (x_n, y_n)이 주어졌을 때 잔차 제곱의 합 ∑i=1n(a2xi+b2−yi)2\sum_{i=1}^n (a_2 x_i + b_2 - y_i)^2을 최소로 만드는 실수 a2a_2와 b2b_2를 찾는다. 동우는 이를 확장해 잔차의 kk제곱의 합 ∑i=1n(akxi+bk−yi)k\sum_{i=1}^n (a_k x_i + b_k - y_i)^k을 00에 가장 가깝게 만드는 실수 aka_k와 bkb_k를 구하도록 했다. 유림이가 너무 어렵다고 하자 동우는 조건 두 가지를 추가했다. k=1k = 1인 경우만 구하고, yy절편이 정해져 있을 때 기울기만 구한다.

유림이를 도와 주어진 bb에 대해 ∑i=1n(a1xi+b−yi)1\sum_{i=1}^n (a_1 x_i + b - y_i)^1의 값을 00에 가장 가깝게 만드는 실수 a1a_1을 구하시오.

입력

첫 줄에 데이터의 개수를 나타내는 정수 nn (1≤n≤1051 \le n \le 10^5)과 yy절편을 나타내는 정수 bb (−109≤b≤109-10^9 \le b \le 10^9)가 주어진다. 두 번째 줄부터 nn개의 줄에 걸쳐 한 줄에 하나씩 점의 좌표를 나타내는 정수 xix_i와 yiy_i (−109≤xi,yi≤109-10^9 \le x_i, y_i \le 10^9)가 주어진다. 같은 점이 여러 번 주어질 수 있다.

출력

첫 번째 줄에 ∑i=1n(a1xi+b−yi)1\sum_{i=1}^n (a_1 x_i + b - y_i)^1의 값을 00에 가장 가깝게 만드는 a1a_1을 출력한다.

답이 정수이면 그대로 출력한다. 정수가 아닌 유리수이면 기약분수 p/qp/q (1≤∣p∣1 \le |p|, 2≤q2 \le q, gcd⁡(∣p∣,q)=1\gcd(|p|, q) = 1)로 약분해 p/q 형태로 출력한다. 00에 가장 가까운 값을 만드는 유리수 a1a_1이 존재함을 증명할 수 있다.

가능한 a1a_1이 여러 개이면 EZPZ를 출력한다.

예제4

  1. 예제 1

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

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

    입력
    6 3
    -1 1
    0 2
    1 4
    -1 1
    2 5
    2 6
    
    예상 출력
    1/3
    
  4. 예제 4

    입력
    1 0
    0 0
    
    예상 출력
    EZPZ