Biorąc pod uwagę 4 punkty na płaszczyznach 2D A, B, C, D, obliczyć obszar regionu przecięcia trójkątów OABi OCD, gdzie Ojest środek płaszczyzny, mieć współrzędną (0, 0).

Algorytmy działające ze stałą złożonością czasową (pod względem operacji arytmetycznych) są zalecane, ale nie wymuszone.

Zasady

• Każdy punkt jest reprezentowany jako dwie liczby rzeczywiste, oznaczające ich współrzędne X i Y.
  • Opcjonalnie, jeśli Twój język programowania (lub pewna biblioteka języka programowania) ma wbudowany Pointtyp lub równoważny, dozwolone jest przyjmowanie Pointobiektu jako danych wejściowych.
• Dane wejściowe podano jako 4 punkty, w formatach, w tym między innymi:
  • Lista 8 współrzędnych.
  • Lista 4 punktów, każdy punkt może być reprezentowany w dowolnym dogodnym formacie.
  • Dwie listy po 2 punkty.
  • itp.
• Nie można zakładać określonej kolejności punktów (kolejność w lewo lub w prawo)
• Nie można zakładać, że punkt Ojest przekazywany jako dane wejściowe. Innymi słowy, program nie może pobierać i wykorzystywać obcych danych wejściowych.
• Nie możesz założyć, że wszystkie punkty są różne. Innymi słowy, trójkąty mogą być zdegenerowane. Musisz także obsłużyć tę sprawę (patrz przypadki testowe poniżej)
• Różnica bezwzględna lub względna musi być mniejsza niż dla przykładowych przypadków testowych poniżej.10-3

Kryteria wygranej

To jest golf golfowy , najkrótsza odpowiedź w bajtach wygrywa!

Przykładowe przypadki testowe

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

Jeśli ktoś chce, oto wyniki dla pierwszej grupy przypadków testowych w dokładnej formie:

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

Zdjęcie ilustracyjne dla przypadku testowego 5 1 1 3 3 4 4 -3(obszar zielonego czworoboku jest oczekiwanym wynikiem):

[ ]

Wolfram Language (Mathematica) , 55 bajtów

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

Wypróbuj online!

Ogoliłem kilka bajtów z banalnej odpowiedzi.

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

Wymiana Areaz DiscretizeRegionpokaże skrzyżowanie.

Nawiasem mówiąc, będzie to działać z dowolnymi simpleksami, nie tylko trójkątami.

-1 bajt dzięki JungHwan Min

Sugestia @ user202729 dodała 4 bajty, ale daje 0 dla zdegenerowanych trójkątów

Python 2 + PIL, 341 318 313 284 270 bajtów

^{Specjalne podziękowania dla Dennisa, który szybko dodał PIL na bajtach TIO
-23 dzięki Panu Xcoderowi}

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

Wypróbuj online! lub Wypróbuj wszystkie przypadki testowe

Aby obliczyć różnicę, należy dosłownie narysować trójkąty i sprawdzić liczbę pikseli namalowanych na obu obrazach.
Ta metoda wstawiła błąd zaokrąglenia, który jest łagodzony przez zwiększenie rozmiaru obrazu.

Wyjaśnienie

#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