Étant donné 4 points sur les plans 2D A, B, C, D, calculez l'aire de la région d'intersection des triangles OABet OCD, où Oest le centre du plan, en ayant les coordonnées (0, 0).

Les algorithmes qui s'exécutent en complexité temporelle constante (en termes d'opérations arithmétiques) sont encouragés, mais pas forcés.

Règles

• Chaque point est représenté par deux nombres réels, dénote leurs coordonnées X et Y.
  • Facultativement, si votre langage de programmation (ou une bibliothèque de votre langage de programmation) a un type intégré Pointou équivalent, il est autorisé à prendre un Pointobjet en entrée.
• L'entrée est donnée en 4 points, dans les formats, y compris mais sans s'y limiter:
  • Une liste de 8 coordonnées.
  • Une liste de 4 points, chaque point peut être représenté dans n'importe quel format pratique.
  • Deux listes de 2 points.
  • etc.
• Vous ne pouvez pas assumer un ordre particulier des points (ordre anti-horaire ou horaire)
• Vous ne pouvez pas supposer que le point Oest passé en entrée. En d'autres termes, le programme ne doit pas prendre et utiliser une entrée étrangère.
• Vous ne pouvez pas supposer que tous les points sont différents. En d'autres termes, les triangles peuvent être dégénérés. Vous devez également gérer ce cas (voir les cas de test ci-dessous)
• La différence absolue ou relative doit être inférieure à celle des exemples de cas de test ci-dessous.10-3

Critères gagnants

C'est le code-golf , la réponse la plus courte en octets gagnant!

Exemples de cas de test

Ax Ay Bx By Cx Cy Dx Dy area

5 1 1 3 -1 0 0 -1 0
5 1 1 3 -1 0 0 0 0
5 1 1 3 0 0 0 0 0
5 1 1 3 3 4 4 -3 4.50418
5 1 1 3 1 2 2 1 1.5
5 1 1 3 -2 5 4 -2 1.74829
5 1 1 3 -2 5 5 4 2.96154
5 1 1 3 3 5 5 4 1.88462
5 1 1 3 3 5 3 1 3.92308
5 1 1 3 3 5 4 -1 5.26619
5 1 1 3 5 1 4 -1 0
5 1 1 3 5 1 1 3 7
1 3 1 3 5 1 1 3 0
1 3 1 3 1 3 1 3 0
4 8 4 -1 -2 6 -2 -3 0

1.2 3.4 -0.3 4.2 5 7.6 -1.1 2.4 2.6210759326188535
3.1 0.6 0.1 7.2 5.2 0.7 0.9 8 9.018496993987977

Si quelqu'un le souhaite, voici les sorties du premier groupe de cas de test sous leur forme exacte:

0
0
0
46375/10296
3/2
1792/1025
77/26
49/26
51/13
23345/4433
0
7
0
0
0

Image d'illustration pour le cas de test 5 1 1 3 3 4 4 -3(la zone du quadrilatère vert est la sortie attendue):

[ ]

Wolfram Language (Mathematica) , 55 octets

0&@@Area@BooleanRegion[And,Simplex[{0{,}}~Join~#]&/@#]&

Essayez-le en ligne!

Rasé quelques octets de la réponse triviale.

%@{{{5, 1}, {1, 3}}, {{3, 4}, {4, -3}}} yields 46375/10296 or 4.504176379

Le remplacement Areapar DiscretizeRegionaffichera l'intersection.

Soit dit en passant, cela fonctionnera avec tous les simplexes, pas seulement les triangles.

-1 octet grâce à JungHwan Min

La suggestion de @ user202729 a ajouté 4 octets, mais elle donne 0 pour les triangles dégénérés

Python 2 + PIL, 341 318 313 284 270 octets

^{Remerciements particuliers à Dennis qui a rapidement ajouté PIL sur TIO
-23 octets grâce à M. Xcoder}

import PIL.Image as I,PIL.ImageDraw as D
l=[i*1000for i in[0,0]+input()+[0,0]]
z=zip(*[[i-min(t)for i in t]for t in l[::2],l[1::2]])
print sum(map(int.__mul__,*map(lambda i,c:D.Draw(i).polygon(c,1)or i.getdata(),map(I.new,'11',[[max(l)-min(l)]*2]*2),[z[:3],z[3:]])))/1e6

Essayez-le en ligne! ou Essayez tous les cas de test

Pour calculer la différence, dessinez littéralement les triangles et vérifiez la quantité de pixels qui sont peints dans les deux images.
Cette méthode a inséré une erreur d'arrondi, qui est adoucie en augmentant la taille de l'image.

Explication

#the image/triangles are enlarged to increase the precision
#a pair of zeros are inserted in the start and at the end, this way "l" will have all 6 points to draw the triangles 
l=[i*1000for i in[0,0]+input()+[0,0]]
#split the input in x and y, where x=l[::2] and y=l[1::2]
#get the smallest number on each list, that will be "0" if there is no negative number, to be used as offset.
#this will be used to overcome the fact that PIL won't draw on negative coords
#zip "x" and "y" lists, to create a list containing the points
z=zip(*[[i-min(t)for i in t]for t in x,y])
#create 2 (B&W) blank images
#where the size is the difference between the smallest and the largest coord.
map(I.new,'11',[[max(l)-min(l)]*2]*2)
#draw both triangles and return the pixel list of each image
map(lambda i,c:D.Draw(i).polygon(c,1)or i.getdata(),<result of previous line>,[z[:3],z[3:]])
#count the amount of overlapping pixels by summing the color of each pixel, if the pixel is "1" in both images, then the triangles are overlapping, then the amount of pixels is divided by the initial enlarging factor squared (1e6)
print sum(map(int.__mul__,*<result of previous line>))/1e6