fork download
copy 
  1. import math
  2. def find(u, par):
  3.  
  4.     if par[u] != u:
  5.         par[u] = find(par[u], par)
  6.     return par[u]
  7.  
  8. def union(u, v, par, size):
  9.     u_root = find(u, par)
  10.     v_root = find(v, par)
  11.  
  12.     if u_root == v_root:
  13.         return 
  14.  
  15.  
  16.     if size[u_root] < size[v_root]:
  17.         par[u_root] = v_root
  18.         size[v_root] += size[u_root]
  19.     else:
  20.         par[v_root] = u_root
  21.         size[u_root] += size[v_root]
  22.  
  23. def ip():
  24.     return map(int,input().split())
  25.  
  26.  
  27.  
  28.  
  29. T=1
  30. T=int(input())
  31. for __ in range(T):
  32.     n=int(input())
  33.     x=[]
  34.     y=[]
  35.     lst=[]
  36.     for _ in range(n):
  37.         a,b=ip()
  38.         x.append(a)
  39.         y.append(b)
  40.         lst.append((a,b))
  41.     # x=[1,1,2]
  42.     # y=[1,2,1]
  43.     # lst=[(1,1),(1,2),(2,1)]
  44.     # n=3
  45.     if n==1:
  46.         print(1)
  47.         continue
  48.  
  49.  
  50.     x.sort()
  51.     y.sort()
  52.  
  53.     mn=(x[-1]-x[0]+1)*(y[-1]-y[0]+1)
  54.     for i in range(n):
  55.         a,b=lst[i]
  56.  
  57.         x0=x[0]
  58.         x1=x[-1]
  59.         y0=y[0]
  60.         y1=y[-1]
  61.  
  62.         if len(x)>1:
  63.             if a==x[-1] and x[-2]!=x[-1]:
  64.                 x1=x[-2]
  65.             if a==x[0] and x[1]!=x[0]:
  66.                 x0=x[1]
  67.         if len(y)>1:
  68.  
  69.             if b==y[-1] and y[-2]!=y[-1]:
  70.                 y1=y[-2]
  71.             if b==x[0] and y[1]!=y[0]:
  72.                 y0=y[1]
  73.         area=(x1-x0+1)*(y1-y0+1)
  74.         if area>n-1:
  75.             mn=min(mn,area)
  76.         elif area==n-1:
  77.             mn=min(mn,area+min(x1-x0+1,y1-y0+1))
  78.  
  79.     print(mn)
  80.  
  81.  
Success #stdin #stdout 0.07s 14180KB
comments (?)
stdin
copy 
7
3
1 1
1 2
2 1
5
1 1
2 6
6 4
3 3
8 2
4
1 1
1 1000000000
1000000000 1
1000000000 1000000000
1
1 1
5
1 2
4 2
4 3
3 1
3 2
3
1 1
2 5
2 2
4
4 3
3 1
4 4
1 2
stdout
copy 
3
32
1000000000000000000
1
6
4
8
https://ideone.com/QL6Uke
language:
Python 3 (python  3.12)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!