Day20200713—點(diǎn)在三角形內(nèi)

文章目錄

• Day20200713—點(diǎn)在三角形內(nèi)
• • 前言
  • 參考
  • 題目
  • • 描述
    • 示例
  • 解題
  • • 關(guān)鍵詞與細(xì)節(jié)
    • 條件
    • 解題思路
  • 算法實(shí)現(xiàn)
  • • 程序代碼
    • 運(yùn)行截圖
  • 思考
  • 后續(xù)

前言

因?yàn)楦鞣N原因，有一段時(shí)間沒有開始計(jì)劃性刷題了。在現(xiàn)在看來，無疑是浪費(fèi)很多時(shí)間。

直到某一天，看到一位大牛每天都有計(jì)劃性地學(xué)習(xí)，也看到了其中一道非常有趣的題，想起了高中刷題的日子。

所以從今天開始，開始計(jì)劃性刷題。

關(guān)于標(biāo)題，是因?yàn)檫@一道算法題的重點(diǎn)在于點(diǎn)在三角形內(nèi)的運(yùn)用。

參考

題目來源

Point in triangle test

雖然沒有使用這個(gè)思路，但是非常具有參考價(jià)值

題目

描述

示例

解題

關(guān)鍵詞與細(xì)節(jié)

不知道動物園的具體位置，動物園在三角形ABC范圍內(nèi)(包括邊界與頂點(diǎn))

3|OA|+2|OB|+|OC|最小,其中點(diǎn)O為動物園

O、A、B、C均為整點(diǎn)，均在同一個(gè)平面

條件

點(diǎn)O在三角形內(nèi)，且滿足3|OA|+2|OB|+|OC|最小

這兩個(gè)條件只保證了點(diǎn)O的3|OA|+2|OB|+|OC|只有一個(gè)最小值

但無法保證只有一個(gè)點(diǎn)O,因?yàn)榭赡艽嬖诙鄠€(gè)點(diǎn)O都具有相同的3|OA|+2|OB|+|OC|最小值。

解題思路

條件1

以三角形的三個(gè)頂點(diǎn)獲取一個(gè)正方形區(qū)域即可，如下：

則點(diǎn)O即在正方形區(qū)域內(nèi)，由于O、A、B、C均為整點(diǎn)，數(shù)量是有限的。

通過條件1獲取點(diǎn)O集合

條件2：點(diǎn)O在三角形區(qū)域內(nèi)

將條件1獲取的集合進(jìn)行篩選，需要滿足條件：點(diǎn)O在三角形內(nèi)

$$\begin{gathered} 1.點(diǎn)O,A,B,C的坐標(biāo)分別為:(x0,y0),(x1,y1),(x2,y2),(x3,y3) \\ ????? \\ 2.如果點(diǎn)O在三角形ABC內(nèi)的話，會滿足以下條件： \\ {S}_{ABO}?OC+S_{ACO}?OB+S_{BCO}?OA=0 \\ ????? \\ 3.已知三角形頂點(diǎn)坐標(biāo)，可以通過以下公式計(jì)算： \\ {S}_{ABC}=(1/2)?(x1y2+x2y3+x3y1?x1y3?x2y1?x3y2) \end{gathered}$$

條件3：取得最小值

有兩個(gè)思路

思路1：使用一個(gè)標(biāo)記對象，當(dāng)出現(xiàn)更小的值時(shí)，將產(chǎn)生該值的對象賦予給標(biāo)記對象

思路2：

使用兩個(gè)集合，集合1存儲所有所有滿足條件1和條件2的點(diǎn)O

集合2存儲對應(yīng)產(chǎn)生的3|OA|+2|OB|+|OC|值。獲得集合2中最小值的索引，返回集合1對應(yīng)索引上的值即可

---

思路1和思路2產(chǎn)生的結(jié)果不同，當(dāng)存在多個(gè)點(diǎn)O時(shí)，思路2，將返回多個(gè)點(diǎn)O，但思路1只能返回一個(gè)點(diǎn)O

由于示例返回一個(gè)即可，所以使用思路1即可

算法實(shí)現(xiàn)

程序代碼

import math class Node(object):def __init__(self,x,y):self.x = xself.y = y class parrot(object):def __init__(self,a,b,c):""" a,b,c is a Node """self.a = aself.b = bself.c = cself.list_node = [self.a,self.b,self.c]def getDist(self,a,b):return math.sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y))def getSum(self,node_o):return 3*self.getDist(node_o,self.a)+\2*self.getDist(node_o,self.b)+self.getDist(node_o,self.c)def areaoftriangle(self,node_a,node_b,node_c):#S=(1/2)*(x1y2+x2y3+x3y1-x1y3-x2y1-x3y2)"""node_a.x node_b.x node_c.xnode_a.y node_b.y node_c.y"""area = (1/2)*abs(node_a.x*node_b.y+node_b.x*node_c.y+node_c.x*node_a.y\-node_a.x*node_c.y-node_b.x*node_a.y-node_c.x*node_b.y)return areadef buildvector(self,node_1,node_2):return Node(node_2.x-node_1.x,node_2.y-node_1.y)def vectorofmultiply(self,k,vector):return Node(k*vector.x,k*vector.y)def vectorofsum(self,vector1,vector2,vector3):return Node(vector1.x+vector2.x+vector3.x,vector1.y+vector2.y+vector3.y)def check_in_out(self,node_o:Node):# Nodevector_oa = self.buildvector(self.a,node_o)vector_ob = self.buildvector(self.b,node_o)vector_oc = self.buildvector(self.c,node_o)# areaarea_aco = self.areaoftriangle(self.a,self.c,node_o)area_bco = self.areaoftriangle(self.b,self.c,node_o)area_abo = self.areaoftriangle(self.a,self.b,node_o)# sum = Sbco*Vector(oa)+Saco*Vector(ob)+Sabo*Vector(oc)=Vector(0,0)sum = self.vectorofsum(self.vectorofmultiply(area_bco,vector_oa),self.vectorofmultiply(area_aco,vector_ob),self.vectorofmultiply(area_abo,vector_oc))if sum.x == 0 and sum.y == 0:return Truereturn Falsedef run(self):list_x,list_y = [],[]for i in self.list_node:list_x.append(i.x)list_y.append(i.y)max_x,min_x = max(list_x),min(list_x)max_y,min_y = max(list_y),min(list_y)result,sumList = [],[]minSum = float('inf')flag = Nonefor i in range(min_x,max_x+1):for j in range(min_y,max_y+1):if self.check_in_out(Node(i,j)):if minSum > self.getSum(Node(i,j)):minSum = self.getSum(Node(i,j))flag = Node(i,j)return flag if __name__ == "__main__":a = Node(0,1)b = Node(0,0)c = Node(2,0)o = Node(1,0)parrotObj = parrot(a,b,c)flag = parrotObj.run()print(flag.x,flag.y)

運(yùn)行截圖

思考

這一道題，更加側(cè)重于數(shù)學(xué)思維，例如三角形面積公式，點(diǎn)在三角形內(nèi)等等知識，都是一個(gè)很好的切入點(diǎn)。

三角形面積公式拓展下去，就有很多知識點(diǎn)，例如海倫公式等等。

而點(diǎn)在三角形內(nèi)，則有重心法等等。

而大多數(shù)題都是側(cè)重于經(jīng)典數(shù)據(jù)結(jié)構(gòu)和經(jīng)典的算法。這也驗(yàn)證了當(dāng)初那句

算法+數(shù)據(jù)結(jié)構(gòu)=程序

算法和數(shù)據(jù)結(jié)構(gòu)都同等重要。

后續(xù)

將會在這段時(shí)間內(nèi)抽出時(shí)間，補(bǔ)充關(guān)于點(diǎn)在三角形內(nèi)的更多方法和證明。

總結(jié)

以上是生活随笔為你收集整理的Day20200713—点在三角形内的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。