fork download
copy 
  1. def f(p):
  2.  x,y=zip(*p);L=(X:=max(x),Y:=max(y)),(X,y:=min(y)),(x:=min(x),Y),(x,y);G=[]
  3.  for Q in p:
  4.   for W in p-{Q}:
  5.    if(Q in L)*(W in L):G={*G,Q,W};continue
  6.    if z:=W[0]-Q[0]:
  7.     S=(W[1]-Q[1])/z;B=W[1]-S*W[0];F=O=0
  8.     for i,h in(0,y),(1,Y):
  9.      if(x<=(h-B)/S<=X)*S:
  10.       O=1
  11.       for u,v in p-{Q,W}:F|=[h<=v<=S*u+B,S*u+B<=v<=h][i]
  12.     if F<O:G={*G,Q,W}
  13.  return G
  14.  
  15. s = [['{{1, 1}, {2, 2}, {3, 3}, {1, 3}}', '{{3, 3}, {1, 3}, {1, 1}}'], ["""{{4.4, 14}, {6.7, 15.25}, {6.9, 12.8}, {2.1, 11.1}, {9.5, 14.9}, 
  16.  {13.2, 11.9}, {10.3, 12.3}, {6.8, 9.5}, {3.3, 7.7}, {0.6, 5.1}, {5.3, 2.4}, 
  17.  {8.45, 4.7}, {11.5, 9.6}, {13.8, 7.3}, {12.9, 3.1}, {11, 1.1}}""", """{{13.8, 7.3}, {13.2, 11.9}, {9.5, 14.9}, {6.7, 15.25}, {4.4, 14}, 
  18.  {2.1, 11.1}, {0.6, 5.1}, {5.3, 2.4}, {11, 1.1}, {12.9, 3.1}}"""], ["""{{1, 0}, {1, 1}, {1, -1}, {0.68957, 0.283647}, {0.909487, 0.644276}, 
  19.  {0.0361877, 0.803816}, {0.583004, 0.91555}, {-0.748169, 0.210483}, 
  20.  {-0.553528, -0.967036}, {0.316709, -0.153861}, {-0.79267, 0.585945},
  21.  {-0.700164, -0.750994}, {0.452273, -0.604434}, {-0.79134, -0.249902}, 
  22.  {-0.594918, -0.397574}, {-0.547371, -0.434041}, {0.958132, -0.499614}, 
  23.  {0.039941, 0.0990732}, {-0.891471, -0.464943}, {0.513187, -0.457062}, 
  24.  {-0.930053, 0.60341}, {0.656995, 0.854205}}""", """{{1, -1}, {1, 1}, {0.583004, 0.91555}, {0.0361877, 0.803816}, 
  25.  {-0.930053, 0.60341}, {-0.891471, -0.464943}, {-0.700164, -0.750994}, 
  26.  {-0.553528, -0.967036}}"""]]
  27.  
  28. for i in s:
  29. 	a, b=map(lambda x:eval(x.replace('{','(').replace('}', ')')), i)
  30. 	assert sorted(f({*a})) == sorted(b)
  31.  
  32. print('tests passed')
Success #stdin #stdout 0.09s 14080KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
tests passed
https://ideone.com/cwHCk8
language:
Python 3 (python  3.12)
created:
2 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!