fork download
copy 
  1. '''Author- Akshit Monga'''
  2. import sys,os,io
  3. input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
  4.  
  5.  
  6. def back(arr,ind,taken,s_taken):
  7.     global ans
  8.     if ind==n:
  9.         ans=[]
  10.         for i in range(n):
  11.             ans.append((arr[i]+1,s_taken[i]+1))
  12.         return True
  13.     for i in range(n):
  14.         if i not in taken:
  15.             for j in childToSweet[i]:
  16.                 if j in s_taken:
  17.                     continue
  18.                 if not j:
  19.                     return False
  20.                 if back(arr+[i],ind+1,taken.union({i}),s_taken+[j]):
  21.                     return True
  22.                 break
  23.     return False
  24.  
  25.  
  26.  
  27. t=int(input())
  28. for _ in range(t):
  29.     print("Case #{}:".format(_+1),end=" ")
  30.     n=int(input())
  31.     children=[]
  32.     for i in range(n):
  33.         x,y=map(int,input().split())
  34.         children.append((x,y))
  35.     sweets=[]
  36.     for i in range(n+1):
  37.         x, y = map(int, input().split())
  38.         sweets.append((x, y))
  39.     childToSweet=[[i for i in range(n+1)] for j in range(n)]
  40.     for i in range(n):
  41.         childToSweet[i].sort(key=lambda x:((children[i][0]-sweets[x][0])**2+(children[i][1]-sweets[x][1])**2,-x))
  42.     ans=None
  43.     back([],0,set(),[])
  44.     if not ans:
  45.         print("IMPOSSIBLE")
  46.     else:
  47.         print("POSSIBLE")
  48.         for i,j in ans:
  49.             sys.stdout.write(str(i)+" "+str(j)+"\n")
Success #stdin #stdout 0.03s 9208KB
comments (?)
stdin
copy 
4
2
-3 0
-1 0
3 0
-2 -1
-2 1
1
0 0
1 1
2 2
3
10 0
-10 0
0 0
0 5
-1 0
5 0
0 -5
2
3 4
3 4
5 7
3 4
5 7
stdout
copy 
Case #1: POSSIBLE
1 3
2 2
Case #2: IMPOSSIBLE
Case #3: POSSIBLE
1 3
2 2
3 4
Case #4: POSSIBLE
1 2
2 3
https://ideone.com/XvqDwZ
language:
Python 3 (python  3.9.5)
created:
2 years ago
visibility:
secret

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!