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: Runtime Error

Solution code:
/usr/bin/python
# -*- coding: utf-8 -*-
import sys
import os
import math
import itertools
import numpy as np
from collections import OrderedDict, deque
from bisect import bisect_left, bisect_right, insort_left, insort_right
sys.setrecursionlimit(10000)

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]


class EndLoop(Exception):
    pass


def debug_print(L):
    for col in L:
        print(col)


def debug_print_joined(L):
    for col in L:
        print("".join(col))


def transpose_matrix(L):
    transposed = list(map(list, zip(*L)))
    return transposed


def solve():
    N, K = map(int, input().split())
    x_coordinates = []
    y_coordinates = []
    for _ in range(N):
        x, y = map(int, input().split())
        x_coordinates.append(x)
        y_coordinates.append(y)

    x_coordinates_comb = []
    y_coordinates_comb = []
    for ele in itertools.combinations(x_coordinates, 2):
        x_coordinates_comb.append(ele)

    for ele in itertools.combinations(y_coordinates, 2):
        y_coordinates_comb.append(ele)

    min_area = 10e18
    for x in x_coordinates_comb:
        for y in x_coordinates_comb:
            cnt = 0
            for i in range(N):
                if min(x) <= x_coordinates[i] <= max(x) and min(y) <= y_coordinates[i] <= max(y):
                    cnt += 1

            if cnt >= K:
                min_area = min(min_area, (max(x) - min(x)) * (max(y) - min(y)))

    print(min_area)


solve()

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <bits/stdc++.h>
#define loop(N) for(int i=0;i<N;i++)
#define vi vector<int>
#define vs vector<string>
#define vl vector<long long int>
#define vpi vector<pair<int,int>>
#define msi map<string,int>
#define mil map<int,long long int>
#define lli long long int
#define plli pair<lli,lli>
using namespace std ;
void ps(string i){
    cout << i << endl;
}

template <class T>
void pt(T s){
    cout << s << endl;
}

void pi(int i){
    cout << i << endl;
}

template <class T>
void pv(vector<T> v){
    loop(v.size()){
        pt<T>(v[i]);
    }
}
/*********************************reused****************************/
int n,k;
plli p[60];
lli state[60];
map<string,lli> s;
lli getSurface(){
    lli minx = -1,maxx = -1,miny = -1,maxy = -1;
    loop(k){
        if(minx == -1){
            minx = p[state[i]].first;
        }else{
            minx = min(p[state[i]].first,minx);
        }
        if(maxx == -1){
            maxx = p[state[i]].first;
        }else{
            maxx = max(p[state[i]].first,maxx);
        }
        if(miny == -1){
            miny = p[state[i]].second;
        }else{
            miny = min(p[state[i]].second,miny);
        }
        if(maxy == -1){
            maxy = p[state[i]].second;
        }else{
            maxy = max(p[state[i]].second,maxy);
        }
    }
    return (maxy-miny)*(maxx-minx);
}
lli dp(){
    plli p[60];
    int maxi = -1;
    lli mini = -1;
    do{
        if(mini == -1){
            mini = getSurface();
        }else{
            mini = min(mini,getSurface());
        }
        int finishi = -1;
        loop(k){
            if(state[n-i-1]!=(n-i-1)){
                state[n-i-1]++;
                finishi = i;
                break;
            }
        }
        if(finishi == -1)
            break;
        loop(finishi){
            state[n-i-1] = state[n-i-2]+1;
        }
    }while(true);

    return mini;

}

bool compare(plli a,plli b){
    return a.first < b.first?true:(a.first > b.first)?false:(a.second <= b.second?true:false);
}
int main()
{
    cin >> n>>k;
    loop(k){
        state[i] = i;
    }
    loop(n){
        lli x,y;
        cin >> x >> y;
        p[i] = make_pair(x,y);
    }
    sort(p,p+n,compare);
    cout <<  dp() << endl;
    return 0;
}

Submission status: Runtime Error

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:
          if f+1 >= t:
            sol = t
            break
          f = mid
          continue
        if f+1 >= t:
          sol = f
          break
        t = mid
      if sol:
        area = (xsorted[sol] - right) * (top - bottom)
        if area < ans:
          ans = area

print ans

Submission status: Runtime Error

Solution code:
nums=input().split()
n=int(nums[0])
k=int(nums[1])
points=[]

for i in range(n):
    temp=input().split()
    points.append([int(temp[0]),int(temp[1])])

rmax=points[0][0]
lmax=points[0][0]
tmax=points[0][1]
bmax=points[0][1]
rmaxp=0
lmaxp=0
tmaxp=0
bmaxp=0
for i in range(1,n):
    if points[i][0]>rmax:
        rmax=points[i][0]
        rmaxp=i
    if points[i][0]<lmax:
        lmax=points[i][0]
        lmaxp=i
    if points[i][1]>tmax:
        tmax=points[i][0]
        tmaxp=i
    if points[i][1]<bmax:
        bmax=points[i][0]
        bmaxp=i

min=(points[rmaxp][0]-points[lmaxp][0])*(points[tmaxp][1]-points[bmaxp][1])
patterns=[]
for i in range(n-k):
    for j in range(n-k-i):
        for k in range(n-k-i-j):
            patterns.append([i,j,k,k-n-i-j-k])
for pattern in patterns:
    copypoints=points
    for i in range(pattern[0]):
        del copypoints[rmaxp]
    for i in range(pattern[1]):
        del copypoints[lmaxp]
    for i in range(pattern[2]):
        del copypoints[tmaxp]
    for i in range(pattern[3]):
        del copypoints[bmaxp]
    ans=(points[rmaxp][0]-points[lmaxp][0])*(points[tmaxp][1]-points[bmaxp][1])
    if ans<min:
        min=ans

print("{0}".format(min))

Submission status: Runtime Error

Solution code:
import itertools

nums = [int(x) for x in input().split()]
N,K = nums[0],nums[1]
x_points = []
y_points = []
points = []

for i in range(N):
    point = [int(x) for x in input().split()]
    x_points.append(point[0])
    y_points.append(point[1])

x_points = sorted(x_points)
c_x_points = {x:i for i,x in enumrate(x_points)}
c_y_points = {y:i for i,y in enumrate(y_points)}

r_c_x_points = {i:x for i,x in c_x_points.items()}
r_c_y_points = {i:y for i,y in c_y_points.items()}

MAX_CX = max(c_x_points.values())
MAX_CY = max(c_y_points.values())

ten_ti = itertools.combinations(MAX_CX,2)
nodo_se = itertools.combinations(MAX_CY,2)

min_prod = 10000000000000000000
for tt in ten_ti:
    for ns in nodo_se:
        cnt = 0
        for point in points:
            cx,cy = c_x_points[point[0]],c_y_points[point[1]]
            if tt[0] <= cx <= tt[1] and ns[0] <= cy <= ns[1]:
                cnt += 1
        if cnt >= K:
            prod = abs(r_c_x_points[tt[0]] - r_c_x_points[tt[1]]) * abs(r_c_y_points[ns[0]] - r_c_y_points[ns[1]])
            min_prod = min(prod,min_prod)
print(min_prod)

Submission status: Runtime Error

Solution code:
inputs = input().split()
N = int(inputs[0])
K = int(inputs[1])

input_list = []

for i in range(N):
    inputs = input().split()
    x = int(inputs[0])
    y = int(inputs[1])
    input_list.append([x, y])

dist_list = []
input_list.sort(key=lambda x: x[0])

for i in range(len(input_list)):
    for j in range(i + 1, len(input_list)):
        if input_list[i][0] != input_list[j][0]:
            dist_list.append([[input_list[i][0], input_list[i][1]], [input_list[j][0],input_list[j][1]], abs((input_list[i][0] - input_list[i][1])**2 - (input_list[j][0] - input_list[j][1])**2)])

dist_list.sort(key=lambda x: x[2])

for dist in dist_list:
    num = 0
    for i in input_list:
        if dist[0][0] <= i[0] and dist[1][0] >= i[0] and ((dist[0][1] <= i[1] and dist[1][1] >= i[1]) or (dist[0][1] >= i[1] and dist[1][1] <= i[1])):
            num += 1
    if num >= K :
        ans = (dist[1][0] - dist[0][0])*abs(dist[1][1]-dist[0][1])
        break

print(ans)

Submission status: Runtime Error

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):
    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: Runtime Error

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:
        left = xsorted[(f+t)//2]
        print f, left, t
        c = 0
        for p in ps:
          if right <= p[0] <= left and bottom <= p[1] <= top:
            c += 1
            if c >= K: break
        else:
          f = left
          continue
        t = left
      area = (xsorted[f] - right) * (top - bottom)
      if area < ans:
        ans = area

print ans

Submission status: Runtime Error

Solution code:

def menseki(S):
    sx=[ss[0] for ss in S]
    sy=[ss[1] for ss in S]

    zahyominmax=[min(sx),max(sx),min(sy),max(sy)]
    return (zahyominmax[1]-zahyominmax[0])*(zahyominmax[3]-zahyominmax[2])



def spaceinput():
    return list(map(int,input().split(" ")))



N,K=spaceinput()

x=[]
for i in range(N):
    x.append(spaceinput())

x=sorted(x,key=lambda s:s[0])

S=x[:K]

sx=[ss[0] for ss in S]
sy=[ss[1] for ss in S]

zahyominmax=[min(sx),max(sx),min(sy),max(sy)]
minmenseki=(zahyominmax[1]-zahyominmax[0])*(zahyominmax[3]-zahyominmax[2])


for i in range(K,len(x)):

    #print(S)
    a=x[i]
    S.append(a)

    #minmenseki=menseki
    for k in range(len(S)):
        bb=S[:k]
        bb.extend(S[k+1:])
        s=menseki(bb)
        if s<minmenseki:
            minmenseki=s
            kmin=k


    #menseki=minmenseki
    del S[kmin]


print(minmenseki)

Submission status: Runtime Error

Solution code:
n,k = input().split()
n = int(n)
k = int(k)
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)

k_ar = np.ones(len(ar),dtype=bool)
while k_ar.sum() > k:
    max_x_idx = np.argmax(ar[:,0])
    min_x_idx = np.argmin(ar[:,0])
    max_y_idx = np.argmax(ar[:,1])
    min_y_idx = np.argmin(ar[:,1])
    
    max_min_xy_idx = [max_x_idx,min_x_idx,max_y_idx,min_y_idx]
    menseki_list = []
    
    for i in max_min_xy_idx:
        tmp_k_ar = k_ar.copy()
        tmp_k_ar[i] = False
        menseki_list.append(menseki_all(ar[tmp_k_ar]))
    
    ar_menseki = np.array(menseki_list)
    delete_idx = max_min_xy_idx[ar_menseki.argmin()]
    
    ar = np.delete(ar,delete_idx,0)
    k_ar = np.ones(len(ar),dtype=bool)

print(menseki_all(ar))

Submission status: Runtime Error

Solution code:
from sys import stdin
n,k = map(int,stdin.readline().split())
a = []
for i in xrange(n):
 a.append(map(int,stdin.readline().split()))
def solve(i,j,u,v):
 cnt = 0
 minx = min(a[i][0],a[j][0])
 maxx =  max(a[i][0],a[j][0])
 miny = min(a[i][1],a[j][1])
 maxy = max(a[i][1],a[j][1])
 
 minx1 = min(a[u][0],a[v][0])
 maxx1 =  max(a[u][0],a[v][0])
 miny1 = min(a[u][1],a[v][1])
 maxy1 = max(a[u][1],a[v][1])
 
 minx = min(minx,minx1)
 miny = min(miny,miny1)
 maxx = max(maxx,maxx1)
 maxy = max(maxy,maxy1)
 #print "solving",i,j,minx,maxx,miny,maxy
 for m in xrange(n):
  if a[m][0]>=minx and a[m][0]<=maxx and a[m][1]>=miny and a[m][1]<=maxy:
   cnt+=1
 #print "has",cnt
 if cnt>=k:
  return (maxx-minx)*(maxy-miny)
 return 10**100
ans = 10**50
for i in xrange(n):
 for j in xrange(n):
  for u in xrange(n):
   ans = min(ans,solve(i,j,u,v))
print ans

Submission status: Runtime Error

Solution code:
from sys import stdin
n,k = map(int,stdin.readline().split())
a = []
for i in xrange(n):
 a.append(map(int,stdin.readline().split()))
def solve(i,j,u,v):
 cnt = 0
 minx = min(a[i][0],a[j][0])
 maxx =  max(a[i][0],a[j][0])
 miny = min(a[i][1],a[j][1])
 maxy = max(a[i][1],a[j][1])
 
 minx1 = min(a[u][0],a[v][0])
 maxx1 =  max(a[u][0],a[v][0])
 miny1 = min(a[u][1],a[v][1])
 maxy1 = max(a[u][1],a[v][1])
 
 minx = min(minx,minx1)
 miny = min(miny,miny1)
 maxx = max(maxx,maxx1)
 maxy = max(maxy,maxy1)
 #print "solving",i,j,minx,maxx,miny,maxy
 for m in xrange(n):
  if a[m][0]>=minx and a[m][0]<=maxx and a[m][1]>=miny and a[m][1]<=maxy:
   cnt+=1
 #print "has",cnt
 if cnt>=k:
  return (maxx-minx)*(maxy-miny)
 return 10**100
ans = 10**50
for i in xrange(n):
 for j in xrange(n):
  for u in xrange(n):
    ans = min(ans,solve(i,j,u,v))
print ans

Submission status: Runtime Error

Solution code:
N,K=spaceinput()

x=[]
for i in range(N):
    x.append(spaceinput())

x=sorted(x,key=lambda s:s[0])

S=x[:K]

sx=[ss[0] for ss in S]
sy=[ss[1] for ss in S]

zahyominmax=[min(sx),max(sx),min(sy),max(sy)]
menseki=(zahyominmax[1]-zahyominmax[0])*(zahyominmax[3]-zahyominmax[2])


for i in range(K,len(x)):
    a=x[i]
    nzahyominmax=zahyominmax[:]
    nzahyominmax[1]=a[0]

    if nzahyominmax[2]>a[1]:
        nzahyominmax[2]=a[1]

    if nzahyominmax[3]<a[1]:
        nzahyominmax[3]=a[1]


    news=(zahyominmax[1]-zahyominmax[0])*(zahyominmax[3]-zahyominmax[2])

    if menseki>news:
        menseki=news


print(menseki)