fork(24) download
copy 
  1. import sys, math, numpy
  2.  
  3.  
  4. def triangleField(pointA, pointB, pointC):
  5.     field = math.fabs(
  6.         ((pointB[0] - pointA[0]) * (pointC[1] - pointA[1]) - (pointB[1] - pointA[1]) * (pointC[0] - pointA[0]))) / 2
  7.     return field
  8.  
  9.  
  10. data = sys.stdin
  11. testCount = int(data.readline())
  12. for test in range(testCount):
  13.     pointsListX = []
  14.     pointsCount = int(data.readline())
  15.     trianglesPoints = []
  16.  
  17.     for line in range(1, pointsCount + 1):
  18.         point = list(map(int, data.readline().split()))  # Te można zamienić na tuple.
  19.         point.append(line)
  20.         pointsListX.append(list(point))
  21.     trianglesCount = int(pointsCount / 3)
  22.     pointStatus = numpy.full(len(pointsListX), False, dtype=object)
  23.  
  24.     for triangle in range(trianglesCount):
  25.  
  26.         pointsListX.sort(key=lambda x: x[0])
  27.         xMax = pointsListX[0]
  28.         pointsListX.remove(xMax)
  29.         xMin = pointsListX[-1]
  30.         pointsListX.remove(xMin)
  31.  
  32.         pointsListX.sort(key=lambda x: x[1])
  33.         yMax = pointsListX[0]
  34.  
  35.         candidates = [xMax, xMin, yMax]
  36.         try:
  37.             yMin = pointsListX[-1]
  38.             candidates.append(yMin)
  39.         except:
  40.             pass
  41.  
  42.         if len(candidates) == 4:
  43.             maxField = 0
  44.             for pointC in candidates:
  45.                 if pointStatus[pointC[2] - 1] != True:
  46.                     field = triangleField(xMax, xMin, pointC)
  47.                     if field > maxField:
  48.                         maxField = field
  49.                         answer3 = pointC
  50.         else:
  51.             answer3 = candidates[2]
  52.  
  53.         myNumbers = [xMax[2], xMin[2], answer3[2]]
  54.         myNumbers.sort()
  55.         print(myNumbers[0], myNumbers[1], myNumbers[2])
  56.         pointsListX.remove(answer3)
  57.         pointStatus[answer3[2] - 1] = True
  58.     print()
Success #stdin #stdout 0.21s 26860KB
comments (?)
stdin
copy 
3
3
0 0
1 2
2 1
6
-2 0
2 0
1 1
-1 1
0 3
0 4
15 
0 40
7 10
-1 8
1 13
14 2
-4 4
-3 13
-14 2
0 35
18 1
-20 0
-5 18
0 30
-18 1
20 0
stdout
copy 
1 2 3

1 2 6
3 4 5

1 11 15
9 10 14
5 8 13
2 6 12
3 4 7
https://ideone.com/QArEgm
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!