Problem:


Score : 400 points

Problem Statement

We have N points in a two-dimensional plane.

The coordinates of the i-th point (1 \leq i \leq N) are (x_i,y_i).

Let us consider a rectangle whose sides are parallel to the coordinate axes that contains K or more of the N points in its interior.

Here, points on the sides of the rectangle are considered to be in the interior.

Find the minimum possible area of such a rectangle.  

Constraints

2 \leq K \leq N \leq 50 

-10^9 \leq x_i,y_i \leq 10^9 (1 \leq i \leq N) 

x_i≠x_j (1 \leq i<j \leq N) 

y_i≠y_j (1 \leq i<j \leq N) 

All input values are integers. (Added at 21:50 JST)  

Input

Input is given from Standard Input in the following format:  

N K  
x_1 y_1
:  
x_{N} y_{N}

Output

Print the minimum possible area of a rectangle that satisfies the condition.  

Sample Input 1

4 4
1 4
3 3
6 2
8 1

Sample Output 1

21

One rectangle that satisfies the condition with the minimum possible area has the following vertices: (1,1), (8,1), (1,4) and (8,4).

Its area is (8-1) × (4-1) = 21.  

Sample Input 2

4 2
0 0
1 1
2 2
3 3

Sample Output 2

1

Sample Input 3

4 3
-1000000000 -1000000000
1000000000 1000000000
-999999999 999999999
999999999 -999999999

Sample Output 3

3999999996000000001

Watch out for integer overflows.  



Sample input:
4 4
1 4
3 3
6 2
8 1


Sample output:
21

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
sx, sy = [], []
for i in range(n):
    x, y = map(int, input().split())
    sx.append((x, i))
    sy.append((y, i))
sx.sort()
sy.sort()
px = [[0] for _ in range(n)]
for cx, (x, i) in enumerate(sx):
    px[i] = cx

acm = [[0] * (n + 1) for _ in range(n + 1)]
for cy, (y, i) in enumerate(sy):
    for cx in range(n):
        acm[cx][cy] = acm[cx - 1][cy] + acm[cx][cy - 1] - acm[cx - 1][cy - 1] + int(px[i] == cx)

ans = 5e18
for lcx in range(n - k + 1):
    for lcy in range(n - k + 1):
        acm_l = acm[lcx - 1][lcy - 1]
        for ucx in range(lcx + k - 1, n):
            for ucy in range(lcy + k - 1, n):
                if acm[ucx][ucy] - acm[ucx][lcy - 1] - acm[lcx - 1][ucy] + acm_l >= k:
                    ans = min(ans, (sx[ucx][0] - sx[lcx][0]) * (sy[ucy][0] - sy[lcy][0]))
                    break
            else:
                continue
            break
print(ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
sx, sy = [], []
for i in range(n):
    x, y = map(int, input().split())
    sx.append((x, i))
    sy.append((y, i))
sx.sort()
sy.sort()
px = [[0] for _ in range(n)]
for cx, (x, i) in enumerate(sx):
    px[i] = cx

acm = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(n):
    xj = px[sy[i][1]]
    for j in range(n):
        acm[i][j] = acm[i - 1][j] + acm[i][j - 1] - acm[i - 1][j - 1] + int(xj == j)

ans = 5e18
for li in range(n):
    for ui in range(li + 1, n):
        for lj in range(n):
            for uj in range(lj + 1, n):
                # print(li, ui, lj, uj)
                # print(acm[ui][uj], acm[ui][lj - 1], acm[li - 1][uj], acm[li - 1][lj - 1])
                if acm[ui][uj] - acm[ui][lj - 1] - acm[li - 1][uj] + acm[li - 1][lj - 1] >= k:
                    ans = min(ans, (sx[ui][0] - sx[li][0]) * (sy[uj][0] - sy[lj][0]))
print(ans)

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
sx, sy = [], []
for i in range(n):
    x, y = map(int, input().split())
    sx.append((x, i))
    sy.append((y, i))
sx.sort()
sy.sort()
px = [[0] for _ in range(n)]
for cx, (x, i) in enumerate(sx):
    px[i] = cx

acm = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(n):
    xj = px[sy[i][1]]
    for j in range(n):
        acm[i][j] = acm[i - 1][j] + acm[i][j - 1] - acm[i - 1][j - 1] + int(xj == j)

ans = 5e18
for li in range(n - k + 1):
    for ui in range(li + k - 1, n):
        for lj in range(n - k + 1):
            for uj in range(lj + k - 1, n):
                # print(li, ui, lj, uj)
                # print(acm[ui][uj], acm[ui][lj - 1], acm[li - 1][uj], acm[li - 1][lj - 1])
                if acm[ui][uj] - acm[ui][lj - 1] - acm[li - 1][uj] + acm[li - 1][lj - 1] >= k:
                    ans = min(ans, (sx[ui][0] - sx[li][0]) * (sy[uj][0] - sy[lj][0]))
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import sys
import itertools


def main():
    n, k = [int(x) for x in sys.stdin.readline().rstrip().split(" ")]

    data = []
    for line in sys.stdin:
        x, y = [int(i) for i in line.rstrip().split(" ")]
        data.append((x, y))


    data_x = list(sorted(data, key=lambda x: (x[0], x[1])))
    data_y = list(sorted(data, key=lambda x: (x[1], x[0])))


    s_min = float("inf")

    for i in range(n - k + 1):
        d = data_x[i:i + k]
        x_max = max(d, key=lambda x: x[0])[0]
        x_min = min(d, key=lambda x: x[0])[0]
        y_max = max(d, key=lambda x: x[1])[1]
        y_min = min(d, key=lambda x: x[1])[1]

        s = (x_max - x_min) * (y_max - y_min)
        s_min = min(s, s_min)
    
    for i in range(n - k + 1):
        d = data_y[i:i + k]
        x_max = max(d, key=lambda x: x[0])[0]
        x_min = min(d, key=lambda x: x[0])[0]
        y_max = max(d, key=lambda x: x[1])[1]
        y_min = min(d, key=lambda x: x[1])[1]

        s = (x_max - x_min) * (y_max - y_min)
        s_min = min(s, s_min)

    print(s_min)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import sys
import itertools


def main():
    n, k = [int(x) for x in sys.stdin.readline().rstrip().split(" ")]

    data = []
    for line in sys.stdin:
        x, y = [int(i) for i in line.rstrip().split(" ")]
        data.append((x, y))


    data_x = list(sorted(data, key=lambda x: (x[0], x[1])))
    data_y = list(sorted(data, key=lambda x: (x[1], x[0])))


    s_min = float("inf")

    for i in range(n - k):
        d = data_x[i:i + k]
        x_max = max(d, key=lambda x: x[0])[0]
        x_min = min(d, key=lambda x: x[0])[0]
        y_max = max(d, key=lambda x: x[1])[1]
        y_min = min(d, key=lambda x: x[1])[1]

        s = (x_max - x_min) * (y_max - y_min)
        s_min = min(s, s_min)
    
    for i in range(n - k):
        d = data_y[i:i + k]
        x_max = max(d, key=lambda x: x[0])[0]
        x_min = min(d, key=lambda x: x[0])[0]
        y_max = max(d, key=lambda x: x[1])[1]
        y_min = min(d, key=lambda x: x[1])[1]

        s = (x_max - x_min) * (y_max - y_min)
        s_min = min(s, s_min)

    print(s_min)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n, k = map(int, input().split())
sx, sy = [], []
for i in range(n):
    x, y = map(int, input().split())
    sx.append((x, i))
    sy.append((y, i))
sx.sort()
sy.sort()
ps = [[0, 0] for _ in range(n)]
for cx, (x, i) in enumerate(sx):
    ps[i][0] = cx
for cy, (y, i) in enumerate(sy):
    ps[i][1] = cy

acm = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(n):
    xj = ps[sy[i][1]][0]
    for j in range(n):
        acm[i][j] = acm[i - 1][j] + acm[i][j - 1] - acm[i - 1][j - 1] + int(xj == j)

# print(acm)

ans = 5e18
for li in range(n - k + 1):
    for ui in range(li + k - 1, n):
        for lj in range(n - k + 1):
            for uj in range(lj + k - 1, n):
                # print(li, ui, lj, uj)
                # print(acm[ui][uj], acm[ui][lj - 1], acm[li - 1][uj], acm[li - 1][lj - 1])
                if acm[ui][uj] - acm[ui][lj - 1] - acm[li - 1][uj] + acm[li - 1][lj - 1] >= k:
                    ans = min(ans, (sx[ui][0] - sx[li][0]) * (sy[uj][0] - sy[lj][0]))
print(ans)

Submission status: Wrong Answer

Solution code:
import math,heapq,collections,sys,numpy
sys.setrecursionlimit(10**7)

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

N,K = LI()
p = []
for i in range(N):
    a,b = LI()
    p.append((a,b,i))
sp = sorted(p)
mi = 10**50
for i in range(N-K+1):
    sp2 = sorted(sp[i:i+K],key=lambda sp2: sp2[1])
    mi = min(mi, (sp[i+K-1][0]  - sp[i][0]) * (sp2[K-1][1]-sp2[0][1]))
    
sp = sorted(p,key=lambda sp2: sp2[1])
for i in range(N-K+1):
    sp2 = sorted(sp[i:i+K])
    mi = min(mi, (sp[i+K-1][1]  - sp[i][1]) * (sp2[K-1][0]-sp2[0][0]))

print(mi)

Submission status: Wrong Answer

Solution code:
import numpy as np

n,m = input().split()
n = int(n)
m = int(m)
xy_list = []
for i in range(n):
    x,y = input().split()
    x = int(x)
    y = int(y)
    xy_list.append([x,y])
    
ar = np.array(xy_list)

def menseki_all(ar):
    max_x = ar[:,0].max()
    min_x = ar[:,0].min()
    max_y = ar[:,1].max()
    min_y = ar[:,1].min()
    return (max_x-min_x)*(max_y-min_y)

menseki = -1
for i in range(n-m):
    tmp_i_ar = ar.copy()
    i_idx = np.argsort(tmp_i_ar[:,0])[:n-i]
    print(tmp_i_ar,i_idx)
    for j in range(n-m-i):
        tmp_j_ar = tmp_i_ar[i_idx].copy()
        j_idx = np.argsort(tmp_j_ar[:,1])[:n-i-j]
        for k in range(n-m-i-j):
            tmp_k_ar = tmp_j_ar[j_idx].copy()
            k_idx = np.argsort(tmp_k_ar[:,0])[k:]
            l = n-m-i-j-k
            tmp_l_ar = tmp_k_ar[k_idx].copy()
            l_idx = np.argsort(tmp_l_ar[:,0])[l:]
            tmp_ar = tmp_l_ar[l_idx]
            tmp_menseki = menseki_all(tmp_ar)
            if menseki == -1:
                menseki = tmp_menseki
            elif menseki > tmp_menseki:
                menseki = tmp_menseki
if menseki == -1:
    menseki = menseki_all(ar)
print(menseki)

Submission status: Wrong Answer

Solution code:
import math,heapq,collections,sys,numpy
sys.setrecursionlimit(10**7)

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

N,K = LI()
p = []
for i in range(N):
    a,b = LI()
    p.append((a,b,i))
    
sp = sorted(p)
mi = 10**50
for i in range(N-K+1):
    sp2 = sorted(sp[i:i+K],key=lambda sp2: sp2[1])
    mi = min(mi, (sp[i+K-1][0]  - sp[i][0]) * (sp2[K-1][1]-sp2[0][1]))
print(mi)

Submission status: Wrong Answer

Solution code:
N, K = map(int, raw_input().split())
ps = []
for i in xrange(N):
  ps.append(map(int, raw_input().split()))

xsorted = zip(*sorted(ps, key=lambda p: p[0]))[0]
ysorted = zip(*sorted(ps, key=lambda p: p[1]))[1]

ans = float('inf')
for i in xrange(N):
  bottom = ysorted[i]
  for j in xrange(i+K-1, N):
    top = ysorted[j]
    for k in xrange(N):
      if k+K-1 >= N:
        break
      right = xsorted[k]
      # 2 bun tansaku
      f, t = k+K-1, N
      sol = None
      while True:
        mid = (f+t)//2
        left = xsorted[mid]
        c = 0
        for p in ps:
          if right <= p[0] <= left and bottom <= p[1] <= top:
            c += 1
            if c >= K: break
        else:
          f = mid
          if f+1 >= t: break
          continue
        sol = t = mid
        if f+1 >= t: break
      if sol:
        area = (xsorted[sol] - right) * (top - bottom)
        if area < ans:
          ans = area

print ans

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())

points = []

for i in range(0,N):
    x,y = map(int,input().split())
    points.append((x,y))

points.sort()

sq = 10E+50

for i in range(0,N):
    if i > N-K-1:
        break
    ymin = points[i][1]
    ymax = points[i][1]
    for j in range(i+1,i+K):
        ymin = min(ymin,points[j][1])
        ymax = max(ymax,points[j][1])
    sq = min(sq,(ymax-ymin) * (points[i+K-1][0]-points[i][0]))

print(sq)

Submission status: Wrong Answer

Solution code:
import numpy as np

n,m = input().split()
n = int(n)
m = int(m)
xy_list = []
for i in range(n):
    x,y = input().split()
    x = int(x)
    y = int(y)
    xy_list.append([x,y])
    
ar = np.array(xy_list)

def menseki_all(ar):
    max_x = ar[:,0].max()
    min_x = ar[:,0].min()
    max_y = ar[:,1].max()
    min_y = ar[:,1].min()
    return (max_x-min_x)*(max_y-min_y)

menseki = -1
for i in range(n-m):
    tmp_i_ar = ar.copy()
    del_i_idx = np.argsort(tmp_i_ar[:,0])[:-(i+1)]
    for j in range(n-m-i):
        tmp_j_ar = np.delete(tmp_i_ar,del_i_idx,0)
        del_j_idx = np.argsort(tmp_j_ar[:,1])[:-(j+1)]
        for k in range(n-m-i-j):
            tmp_k_ar = np.delete(tmp_j_ar,del_j_idx,0)
            del_k_idx = np.argsort(tmp_k_ar[:,0])[k+1:]
            l = n-m-i-j-k
            tmp_l_ar = np.delete(tmp_k_ar,del_k_idx,0)
            del_l_idx = np.argsort(tmp_l_ar[:,0])[l+1:]
            tmp_ar = np.delete(tmp_l_ar,del_l_idx,0)
            tmp_menseki = menseki_all(tmp_ar)
            if menseki == -1:
                menseki = tmp_menseki
            elif menseki > tmp_menseki:
                menseki == tmp_menseki
if menseki == -1:
    menseki = menseki_all(ar)
print(menseki)

Submission status: Wrong Answer

Solution code:
import math,heapq,collections,sys,numpy
sys.setrecursionlimit(10**7)

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

N,K = LI()
p = []
for i in range(N):
    a,b = LI()
    p.append((a,b,i))

sp = sorted(p)

mi = 10**50
for i in range(N-K+1):
    mi = min(mi, (sp[i+K-1][0]  - sp[i][0]) * (abs(sp[i+K-1][1] - sp[i][1])))
print(mi)

Submission status: Wrong Answer

Solution code:
N,K=map(int,raw_input().split(' '))

points=[()]*N
for i in range(N):
    x,y=map(int,raw_input().split(' '))
    points[i]=(x,y)

def inc(p1,p2):
    if p1[0]<p2[0]:
        x_min=p1[0]
        x_lrg=p2[0]
    else:
        x_min=p2[0]
        x_lrg=p1[0]

    if p1[1]<p2[1]:
        y_min=p1[1]
        y_lrg=p2[1]
    else:
        y_min=p2[1]
        y_lrg=p1[1]
        
    k=0
    for i in range(N):
        x,y=points[i]
        if x_min<=x<=x_lrg and y_min<=y<=y_lrg:
            k+=1
    return k

#tmp=()
s=float('inf')
for i in range(N):
    p1=points[i]
    for j in range(N):
        px=points[j]
        for k in range(N):
            if i==j or i==k:
                continue
            py=points[k]
            absx=abs(p1[0]-px[0])
            absy=abs(p1[1]-py[1])
            t=absx*absy
            if(inc(p1,(px[0],py[1]))>=K and t<s):
                s=t
                #tmp=(p1,(px[0],py[1]))
print s

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
https://beta.atcoder.jp/contests/abc075/tasks/abc075_d

"""
import sys
from sys import stdin
input = stdin.readline


def solve(points, N, K):
    max_x = float('-inf')
    max_y = float('-inf')
    min_x = float('inf')
    min_y = float('inf')
    remove = N - K
    if remove == 0:
        for x, y in points:
            if x > max_x:
                max_x = x
            if x < min_x:
                min_x = x
            if y > max_y:
                max_y = y
            if y < min_y:
                min_y = y
        return (max_x - min_x) * (max_y - min_y)

    while remove:
        max_x = float('-inf')
        max_y = float('-inf')
        min_x = float('inf')
        min_y = float('inf')

        distance = [float('inf')] * len(points)
        for x, y in points:
            if x > max_x:
                max_x = x
            if x < min_x:
                min_x = x
            if y > max_y:
                max_y = y
            if y < min_y:
                min_y = y
        c_x = (max_x + min_x) / 2
        c_y = (max_y + min_y) / 2

        for i, (x, y) in enumerate(points):
            d = (x - c_x)**2 + (y - c_y)**2
            distance[i] = d

        max_d = max(distance)
        ind = distance.index(max_d)
        points.pop(ind)
        remove -= 1


    max_x = float('-inf')
    max_y = float('-inf')
    min_x = float('inf')
    min_y = float('inf')

    for x, y in points:
        if x > max_x:
            max_x = x
        if x < min_x:
            min_x = x
        if y > max_y:
            max_y = y
        if y < min_y:
            min_y = y

    return (max_x - min_x) * (max_y - min_y)



def main(args):
    N, K = map(int, input().split())
    points = []
    for _ in range(N):
        points.append([int(x) for x in input().split()])

    points.sort()
    #points.sort(key=lambda x: x[1])
    result = solve(points, N, K)
    print(result)







if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Wrong Answer

Solution code:
import math,heapq,collections,sys,numpy
sys.setrecursionlimit(10**7)

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

N,K = LI()
p = []
for i in range(N):
    a,b = LI()
    p.append((a,b,i))

sp = sorted(p)

mi = 10**20
for i in range(N-K+1):
    mi = min(mi, (sp[i+K-1][0]  - sp[i][0]) * (abs(sp[i+K-1][1] - sp[i][1])))
print(mi)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())

points = []

for i in range(0,N):
    x,y = map(int,input().split())
    points.append((x,y))

points.sort()

sq = 10E+50

for i in range(0,N):
    if i > N-K:
        break
    ymin = points[i][1]
    ymax = points[i][1]
    for j in range(i+1,i+K):
        ymin = min(ymin,points[j][1])
        ymax = max(ymax,points[j][1])
    sq = min(sq,(ymax-ymin) * (points[i+K-1][0]-points[i][0]))

print(sq)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
points = []
pointsx = []
pointsy = []
for _ in range(N):
    x, y = map(int, input().split())
    points.append((x, y))
    pointsy.append((y, x))
pointsx = points[:]
pointsx.sort()
pointsy.sort()
pointsy = list(map(lambda p: (p[1], p[0]), pointsy))

def check(pa, pb):
    xa, ya = pa
    xb, yb = pb
    if xa > xb:
        xa, xb = xb, xa
    if ya > yb:
        ya, yb = yb, ya
 
    res = points[:]
    res = filter(lambda p: p[0] >= xa and p[0] <= xb and p[1] >= ya and p[1] <= yb, res)
    
    return list(res)
 
ans = int(9e30)
for a in range(N-1):
    for b in range(a+1, N):
        x1 = pointsx[a][0]
        x2 = pointsx[b][0]
        for c in range(N-1):
            for d in range(a+1, N):
                y1 = pointsy[c][1]
                y2 = pointsy[d][1]
                pa = (x1, y1)
                pb = (x2, y2)
                poss = check(pa, pb)
                if len(poss) >= K:
                    tmp = abs(pa[0] - pb[0]) * abs(pa[1] - pb[1])
                    ans = min(ans, tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
points = []
pointsx = []
pointsy = []
for _ in range(N):
    x, y = map(int, input().split())
    points.append((x, y))
    pointsy.append((y, x))
pointsx = points[:]
pointsx.sort()
pointsy.sort()
pointsy = list(map(lambda p: (p[1], p[0]), pointsy))

def check(pa, pb):
    xa, ya = pa
    xb, yb = pb
    if xa > xb:
        xa, xb = xb, xa
    if ya > yb:
        ya, yb = yb, ya
 
    res = points[:]
    res = filter(lambda p: p[0] >= xa and p[0] <= xb and p[1] >= ya and p[1] <= yb, res)
    
    return list(res)
 
ans = int(9e20)
for a in range(N-1):
    for b in range(a+1, N):
        x1 = pointsx[a][0]
        x2 = pointsx[b][0]
        for c in range(N-1):
            for d in range(a+1, N):
                y1 = pointsy[c][1]
                y2 = pointsy[d][1]
                pa = (x1, y1)
                pb = (x2, y2)
                poss = check(pa, pb)
                if len(poss) >= K:
                    tmp = abs(pa[0] - pb[0]) * abs(pa[1] - pb[1])
                    ans = min(ans, tmp)
print(ans)

Submission status: Wrong Answer

Solution code:
N, K = map(int, raw_input().split())
ps = []
for i in xrange(N):
  ps.append(map(int, raw_input().split()))

xsorted = zip(*sorted(ps, key=lambda p: p[0]))[0]
ysorted = zip(*sorted(ps, key=lambda p: p[1]))[1]

ans = float('inf')
for i in xrange(N):
  bottom = ysorted[i]
  for j in xrange(i+K-1, N):
    top = ysorted[j]
    for k in xrange(N):
      if k+K-1 >= N:
        break
      right = xsorted[k]
      # 2 bun tansaku
      f, t = k+K-1, N
      while f+1 < t:
        mid = (f+t)//2
        left = xsorted[mid]
        c = 0
        for p in ps:
          if right <= p[0] <= left and bottom <= p[1] <= top:
            c += 1
            if c >= K: break
        else:
          f = mid
          continue
        t = mid
      area = (xsorted[f] - right) * (top - bottom)
      if area < ans:
        ans = area

print ans

Submission status: Wrong Answer

Solution code:
import math
N,K = input().split()
N,K = int(N),int(K)
points = []
distance = []
# dimx = []
# dimy = []
for n in range(N):
    tmp = list(map(int,input().split()))
    points.append(tmp)


for k in range(len(points)):
    l = k+1
    while l < len(points):
        dist = math.sqrt( (points[k][0]-points[l][0])**2
                         +(points[k][1]-points[l][1])**2)
        distance.append([dist,points[k],points[l]])
        l += 1
distance.sort()

def culSquare(point1,point2):   
    return abs(point1[0]-point2[0])*abs(point1[1]-point2[1])

def solver(distance,K):
    if K == 2:
        return culSquare(distance[0][1],distance[0][2])
    else:
        countK = 0
        for _ in distance:
            minx = min(_[1][0],_[2][0])
            maxx = max(_[1][0],_[2][0])
            miny = min(_[1][1],_[2][1])
            maxy = max(_[1][1],_[2][1])
            for __ in points:
                if minx < __[0] and __[0] < maxx and miny < __[1] and __[1] < maxy:
                    countK += 1
            if K <= countK:
                return culSquare(_[1],_[2])


ans = solver(distance,K)
print(ans)

Submission status: Wrong Answer

Solution code:
s = input().split(" ")
N = int(s[0])
K = int(s[1])
x = []
y = []
for i in range(N):
    s = input().split(" ")
    x.append(int(s[0]))
    y.append(int(s[1]))
xs = x
xs.sort()
ys = y
ys.sort()
res = 4 * 10**18
i = 0
while i < N:
    j = i + 1
    while j < N:
        k = 0
        while k < N:
            l = k + 1
            while l < N:
                cnt = 0
                for m in range(N):
                    if xs[i] <= x[m] and x[m] <= xs[j] and ys[k] <= y[m] and y[m] <= ys[l]:
                        cnt += 1
                if cnt >= K:
                    res = min(res, (xs[j] - xs[i]) * (ys[l] - ys[k]))
                l += 1
            k += 1
        j += 1
    i += 1
print(res)

Submission status: Wrong Answer

Solution code:
N,K=map(int,raw_input().split(' '))

points=[()]*N
for i in range(N):
    x,y=map(int,raw_input().split(' '))
    points[i]=(x,y)

def inc(p1,p2):
    if p1[0]<p2[0]:
        x_min=p1[0]
        x_lrg=p2[0]
    else:
        x_min=p2[0]
        x_lrg=p1[0]

    if p1[1]<p2[1]:
        y_min=p1[1]
        y_lrg=p2[1]
    else:
        y_min=p2[1]
        y_lrg=p1[1]
        
    k=0
    for i in range(N):
        x,y=points[i]
        if x_min<=x<=x_lrg and y_min<=y<=y_lrg:
            k+=1
    return k

#tmp=()
s=float('inf')
for i in range(N):
    p1=points[i]
    for j in range(N):
        px=points[j]
        for k in range(N):
            if i==j==k:
                continue
            py=points[k]
            absx=abs(p1[0]-px[0])
            absy=abs(p1[1]-py[1])
            t=absx*absy
            if(inc(p1,(px[0],py[1]))>=K and t<s):
                s=t
                #tmp=(p1,(px[0],py[1]))
print s

Submission status: Wrong Answer

Solution code:
N, K = map(int, input().split())
points = [tuple(map(int, input().split())) for i in range(N)]

ptsX = sorted(points, key=lambda t: t[0])
ptsY = sorted(points, key=lambda t: t[1])

ans = float('inf')
for sideL in range(N):
    for sideR in range(sideL + 1, N):
        for sideB in range(N):
            for sideT in range(sideB + 1, N):

                area = (ptsX[sideR][0] - ptsX[sideL][0]) * (ptsY[sideT][1] - ptsY[sideB][1])

                setX = set(ptsX[sideL:sideR + 1])
                setY = set(ptsX[sideB:sideT + 1])
                num = len(setX & setY)

                if num == K:
                    ans = min(ans, area)

print(ans)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())

points = []

for i in range(0,N):
    x,y = map(int,input().split())
    points.append((x,y))

points.sort()

sq = 10E+30

for i in range(0,1):
    ymin = points[i][1]
    ymax = points[i][1]
    for j in range(i+1,i+K):
        ymin = min(ymin,points[j][1])
        ymax = max(ymax,points[j][1])
    sq = min(sq,(ymax-ymin) * (points[i+K-1][0]-points[i][0]))

print(sq)

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
points1 = []
points2 = []
for i in range(N):
	x,y = tuple((map(int,input().split())))
	points1.append((x,y))
	points2.append(y)
points1.sort()
points2.sort()

xDict = {}
index = 0
for x,y in points1:
	if index in xDict:
		if xDict[index] != x:
			index += 1
			xDict[index] = x
	else:
		xDict[index] = x

yDict = {}
index = 0
for y in points2:
	if index in yDict:
		if yDict[index] != y:
			index += 1 
			yDict[index] = y
	else:
		yDict[index] = y

nPoints = [[0 for j in range(len(yDict))] for i in range(len(xDict))]

for kx,vx in xDict.items():
	for ky,vy in yDict.items():
		exists = 1 if (vx,vy) in points1 else 0
		if kx == 0 and ky == 0:
			nPoints[kx][ky] += exists
		elif kx == 0 and ky > 0:
			nPoints[kx][ky] += nPoints[kx][ky-1] + exists
		elif kx > 0 and ky == 0:
			nPoints[kx][ky] += nPoints[kx-1][ky] + exists
		else:
			nPoints[kx][ky] += nPoints[kx-1][ky] + nPoints[kx][ky-1] - nPoints[kx-1][ky-1] + exists

ans = -1
for x1 in range(len(xDict)):
	for x2 in range(x1+1):
		for y1 in range(len(yDict)):
			for y2 in range(y1+1):
				point = nPoints[x1][y1]
				if x2 > 0:
					point -= nPoints[x2-1][y1]
				if y2 > 0:
					point -= nPoints[x1][y2-1]
				if x2 > 0 and y2 > 0:
					point += nPoints[x2-1][y2-1]
				if point >= K:
					area = (xDict[x1]-xDict[x2]) * (yDict[y1]-yDict[y2])
					if ans < 0:
						ans = area
					else:
						ans = min(ans, area)
print(area)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import copy

n, k = [int(i) for i in input().split()]
num_list_x = [[int(i) for i in input().split()] for _ in range(n)]
num_list_x.sort()
curr_square = float("inf")

for pos in range(n - k + 1):
    for edge_x in range(pos + k - 1, n):
        distance_x = num_list_x[edge_x][0] - num_list_x[pos][0]
        num_list_y = copy.deepcopy(num_list_x[pos:edge_x+1])
        num_list_y.sort(key=lambda number: number[1])
        distance_y = num_list_y[-1][1] - num_list_y[0][1]
        curr_square = min(curr_square, distance_x * distance_y)

num_list_y = copy.deepcopy(num_list_x)
num_list_y.sort(key=lambda number: number[1])

for pos in range(n - k + 1):
    for edge_y in range(pos + k - 1, n):
        distance_y = num_list_y[edge_y][1] - num_list_y[pos][1]
        num_list_x = copy.deepcopy(num_list_y[pos:edge_y+1])
        num_list_x.sort()
        distance_x = num_list_x[-1][0] - num_list_x[0][0]
        curr_square = min(curr_square, distance_x * distance_y)

print(curr_square)

Submission status: Wrong Answer

Solution code:
n,K = map(int,input().split())

x,y = [],[]
xx,yy = [],[]

for _ in range(n):
    X,Y = map(int,input().split())

    x.append(X)
    xx.append(X)
    y.append(Y)
    yy.append(Y)

xx.sort()
yy.sort()

ans = 10**10
for i in range(n):
    for j in range(i):
        lx,rx = xx[j],xx[i]

        num = [0 for _ in range(n+1)]
        for k in range(n):
            if lx <= x[k] <= rx:
                num[yy.index(y[k])+1] += 1

        for k in range(n):
            num[k+1] += num[k]

        for k in range(n):
            for l in range(k):
                ly,ry = yy[l],yy[k]

                if num[k+1] - num[l] >= K:
                    ans = min(ans, (rx-lx)*(ry-ly))

print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python

import sys
from itertools import permutations


def rangeof(arr):
    return max(arr) - min(arr)


def within(a, aa):
    if(aa[0] <= a and a <= aa[1]):
        return True
    if(aa[1] <= a and a <= aa[0]):
        return True

    return False


(N, K) = [int(x) for x in input().split(" ")]

x = []
y = []

for i in range(0, N):
    (x_, y_) = [int(x) for x in input().split(" ")]
    x.append(x_)
    y.append(y_)

minArea = float("inf")
for xcand in permutations(x, 2):
    for ycand in permutations(x, 2):
        pix_in_the_box = 0
        for i in range(0, N):
            if(within(x[i], xcand) and within(y[i], ycand)):
                pix_in_the_box += 1
        if(pix_in_the_box >= K):
            area = abs(rangeof(xcand) * rangeof(ycand))
            if(minArea > area):
                minArea = area

print(minArea)

Submission status: Wrong Answer

Solution code:
N,K=map(int,raw_input().split(' '))

points=[()]*N
for i in range(N):
    x,y=map(int,raw_input().split(' '))
    points[i]=(x,y)

def inc(p1,p2):
    if p1[0]<p2[0]:
        x_min=p1[0]
        x_lrg=p2[0]
    else:
        x_min=p2[0]
        x_lrg=p1[0]

    if p1[1]<p2[1]:
        y_min=p1[1]
        y_lrg=p2[1]
    else:
        y_min=p2[1]
        y_lrg=p1[1]
        
    k=0
    for i in range(N):
        x,y=points[i]
        if x_min<=x<=x_lrg and y_min<=y<=y_lrg:
            k+=1
    return k

s=float('inf')
for i in range(N):
    p1=points[i]
    for j in range(N):
        if j==i:
            continue
        px=points[j]
        for k in range(N):
            if k==j or k==i:
                continue
        py=points[k]
        absx=abs(p1[0]-px[0])
        absy=abs(p1[1]-py[1])
        t=absx*absy
        pn=[0,0]
        if p1[0]>px[0]:
            pn[0]=p1[0]-absx
        else:
            pn[0]=p1[0]+absx
        if p1[1]>py[1]:
            pn[1]=p1[1]-absy
        else:
            pn[1]=p1[1]+absy
        if(inc(p1,pn)>=K and t<s):
            s=t
print s

Submission status: Wrong Answer

Solution code:
N,K = map(int,input().split())
points1 = []
points2 = []
for i in range(N):
	x,y = tuple((map(int,input().split())))
	points1.append((x,y))
	points2.append((y,x))
points1.sort()
points2.sort()

xDict = {}
index = 0
for x,y in points1:
	if index in xDict:
		if xDict[index] != x:
			index += 1
			xDict[index] = x
	else:
		xDict[index] = x

yDict = {}
index = 0
for y,x in points2:
	if index in yDict:
		if yDict[index] != y:
			index += 1 
			yDict[index] = y
	else:
		yDict[index] = y

nPoints = [[0 for j in range(len(yDict))] for i in range(len(xDict))]

for kx,vx in xDict.items():
	for ky,vy in yDict.items():
		exists = 1 if (vx,vy) in points1 else 0
		if kx == 0 and ky == 0:
			nPoints[kx][ky] += exists
		elif kx == 0 and ky > 0:
			nPoints[kx][ky] += nPoints[kx][ky-1] + exists
		elif kx > 0 and ky == 0:
			nPoints[kx][ky] += nPoints[kx-1][ky] + exists
		else:
			nPoints[kx][ky] += nPoints[kx-1][ky] + nPoints[kx][ky-1] - nPoints[kx-1][ky-1] + exists

ans = -1
for x1 in range(len(xDict)):
	for x2 in range(x1+1):
		for y1 in range(len(yDict)):
			for y2 in range(y1+1):
				point = nPoints[x1][y1]
				if x2 > 0:
					point -= nPoints[x2-1][y1]
				if y2 > 0:
					point -= nPoints[x1][y2-1]
				if x2 > 0 and y2 > 0:
					point += nPoints[x2-1][y2-1]
				if point >= K:
					area = (xDict[x1]-xDict[x2]) * (yDict[y1]-yDict[y2])
					if ans < 0:
						ans = area
					else:
						ans = min(ans, area)
print(area)