Diberi 4 poin pada bidang 2D A, B, C, D, hitung luas wilayah persimpangan segitiga OABdan OCD, di mana Opusat pesawat, memiliki koordinat (0, 0).

Algoritma yang berjalan dalam kompleksitas waktu konstan (dalam hal operasi aritmatika) didorong, tetapi tidak dipaksakan.

Aturan

• Setiap titik direpresentasikan sebagai dua bilangan real, menunjukkan koordinat X dan Y mereka.
  • Secara opsional, jika bahasa pemrograman Anda (atau pustaka dari bahasa pemrograman Anda) memiliki Pointtipe bawaan atau yang setara, itu diperbolehkan untuk mengambil Pointobjek sebagai input.
• Input diberikan sebagai 4 poin, dalam format, termasuk tetapi tidak terbatas pada:
  • Daftar 8 koordinat.
  • Daftar 4 poin, masing-masing poin dapat direpresentasikan dalam format yang mudah.
  • Dua daftar 2 poin.
  • dll.
• Anda tidak dapat mengasumsikan pemesanan titik tertentu (urutan berlawanan arah jarum jam atau urutan searah jarum jam)
• Anda tidak dapat mengasumsikan bahwa titik Odilewatkan sebagai input. Dengan kata lain, program tidak boleh mengambil dan menggunakan input asing.
• Anda tidak dapat menganggap semua poin berbeda. Dengan kata lain, segitiga mungkin akan menurun. Anda juga harus menangani kasing (lihat kasing di bawah)
• Perbedaan absolut atau relatif harus kurang dari untuk kasus uji sampel di bawah ini.10-3

Kriteria menang

Ini adalah kode-golf , jawaban terpendek dalam byte menang!

Contoh uji kasus

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

Jika ada yang mau, berikut adalah output untuk kelompok kasus uji pertama dalam bentuk yang tepat:

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

Gambar ilustrasi untuk test case 5 1 1 3 3 4 4 -3(bidang segi empat hijau adalah output yang diharapkan):

[ ]

Bahasa Wolfram (Mathematica) , 55 byte

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

Cobalah online!

Mencukur beberapa byte dari jawaban sepele.

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

Mengganti Areadengan DiscretizeRegionakan menunjukkan persimpangan.

Ngomong-ngomong, ini akan bekerja dengan simpleks apa pun, bukan hanya segitiga.

-1 Byte terima kasih kepada JungHwan Min

Saran @ user202729 menambahkan 4 byte tetapi membuatnya menghasilkan 0 untuk segitiga yang merosot

Python 2 + PIL, 341 318 313 284 270 byte

^{Terima kasih khusus kepada Dennis yang segera menambahkan PIL pada TIO
-23 byte, terima kasih kepada Tn. 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

Cobalah online! atau Coba semua test case

Untuk menghitung perbedaannya, gambarlah segitiga secara harfiah dan periksa jumlah piksel yang dicat pada kedua gambar.
Metode ini memasukkan kesalahan pembulatan, yang diperlunak dengan meningkatkan ukuran gambar.

Penjelasan

#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