python如何實現(xiàn)最小矩形覆蓋問題
更新時間：2023年08月09日 08:51:26 作者：椰子奶糖
這篇文章主要介紹了python如何實現(xiàn)最小矩形覆蓋問題,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教
python實現(xiàn)最小矩形覆蓋
Description
給定一些點的坐標，要求求能夠覆蓋所有點的最小面積的矩形，
輸出所求矩形的面積和四個頂點坐標
Input
第一行為一個整數(shù)n（3<=n<=50000）
從第2至第n+1行每行有兩個浮點數(shù)，表示一個頂點的x和y坐標，不用科學計數(shù)法
Output
第一行為一個浮點數(shù)，表示所求矩形的面積（精確到小數(shù)點后5位），
接下來4行每行表示一個頂點坐標，要求第一行為y坐標最小的頂點，
其后按逆時針輸出頂點坐標.如果用相同y坐標，先輸出最小x坐標的頂點
Sample Input
6 1.0 3.00000 1 4.00000 2.0000 1 3 0.0000 3.00000 6 6.0 3.0
Sample Output
18.00000 3.00000 0.00000 6.00000 3.00000 3.00000 6.00000 0.00000 3.00000
實際上它我們py老師布置的小作業(yè)，用py寫
編寫一個平面二維點集類，要求這個類的實例對象（也就是一個點）能夠計算到另一個點的距離；再編寫一個函數(shù)，能夠計算覆蓋一系列點的最小矩形
思路：找到凸包->旋轉卡殼->計算頂點->輸出
建議用編輯器打開，個人不是很喜歡簡書這里的代碼高亮風格
from math import sqrt
import random
import math
class Point(object):
def __init__(self, x=0, y=0):
self.x = x
self.y = y
def distance_to(self, other):
dx = self.x - other.x
dy = self.y - other.y
return sqrt(dx ** 2 + dy ** 2)
# 計算兩點相對于X軸的（cos）
def angle_cos(self, other):
# cos = dx/dis(self,other)
cos = (other.x - self.x)/self.distance_to(other)
return cos
def __str__(self):
return '(%s, %s)' % (str(self.x), str(self.y))
# 找到極坐標系原點
def get_bottom_point(points):
bot_point = points[0]
temp = 0
for i in range(1, len(points)):
# 找到最左下角的點作為極坐標系原點
if bot_point.y > points[i].y or (bot_point.y == points[i].y and bot_point.x > points[i].x):
bot_point = points[i]
temp = i
# 刪除作為原點的那個點
del(points[temp])
return bot_point, points
# 極坐標排序，cos,從大到小
def sort_polar_angle_cos(points, bot_point):
dic = dict()
for point in points:
dic[bot_point.angle_cos(point)] = point
# for key,value in dic.items():
# print("{}:{}".format(key,value))
# for key ,value in [(k,dic[k]) for k in sorted(dic.keys(),reverse=True)]:
# print("{}::::::{}".format(key,value))
return [dic[k] for k in sorted(dic.keys(), reverse=True)]
# 叉積
def cross_product(p1, p2, p3):
x1 = p2.x-p1.x
y1 = p2.y-p1.y
x2 = p3.x-p1.x
y2 = p3.y-p1.y
return (x1*y2-x2*y1)
# Graham掃描法計算凸包
def graham_scan(points, bot_point):
# 凸包列表，先加前三個
con_list = []
con_list.append(bot_point)
con_list.append(points[0])
con_list.append(points[1])
# 尋找其他凸包上的點
for i in range(2, len(points)-1):
cro = cross_product(con_list[-2], con_list[-1], points[i])
if cro > 0:
con_list.append(points[i])
elif cro < 0:
con_list.pop()
con_list.append(points[i])
# 最后一個點也一定在凸包中
con_list.append(points[-1])
# # 打印所有凸包點坐標
# for each in con_list:
# print(each)
return con_list
# 找到最小矩形
def find_min_ret(con_list):
rec_area = 10000
rec_height = 0
rec_dot = []
rec_po = []
f_po = con_list[0]
for i in range(1, len(con_list)):
max_po = 0
min_po = 0
# 最大三角形面積，用于求高
max_height = 0
# 底邊長
bot_length = 0
# 最大點積與最小點積
max_dot = 0
min_dot = 10000
s_po = con_list[i]
for t_po in con_list:
# 需要改
height = get_area_by_po(f_po, s_po, t_po)/f_po.distance_to(s_po)
# print("height={}".format(height))
if height > max_height:
max_height = height
# 點積求投影長度，同樣存最值？倆？
# 向量w
x1 = (s_po.x - f_po.x)
y1 = (s_po.y - f_po.y)
# 向量v
x2 = (t_po.x - f_po.x)
y2 = (t_po.y - f_po.y)
# 點積
dot = x1*x2+y1*y2
# print("dot={}".format(dot/f_po.distance_to(s_po)))
if dot > max_dot:
max_dot = dot
max_po = t_po
if dot < min_dot:
min_dot = dot
min_po = t_po
# 由于是遍歷，故此min(max_dot) = 底邊^(qū)2 max(min_dot) = 0
bot_length = (max_dot-min_dot)/f_po.distance_to(s_po)
# 矩形面積 = 底*高
area = bot_length*max_height
if rec_area > area:
rec_area = area
# 記錄疑似最小矩形的信息
rec_height = max_height
rec_po = [f_po, s_po, max_po, min_po]
rec_dot = [max_dot, min_dot]
# 下一輪
f_po = s_po
# # 根據(jù)數(shù)據(jù)計算頂點坐標
# for each in rec_po:
# print("rec_po={}".format(each))
# print("rec_dot={}\nrec_height={}".format(rec_dot,rec_height))
rec_po = get_point_list(rec_po, rec_dot, rec_height)
return round(rec_area,10), rec_po
# 叉積求四邊形面積
def get_area_by_po(p1, p2, p3):
# 則平行四邊形面積=[(x2y3-x3y2)-(x1y3-x3y1)+(x1y2-x2y1)]
return (p2.x*p3.y-p3.x*p2.y) - (p1.x*p3.y-p3.x*p1.y) + (p1.x*p2.y-p2.x*p1.y)
# 得到矩形頂點坐標
def get_point_list(rec_po, rec_dot, rec_height):
# rec_height = max_height
# rec_po = [f_po, s_po, max_po, min_po]
# rec_dot = [max_dot, min_dot]
x1 = rec_po[1].x - rec_po[0].x
y1 = rec_po[1].y - rec_po[0].y
# print("max_dot={}\nmin_dot={}".format(rec_dot[0],rec_dot[1]))
# 這么算會存在精度問題，可用round(rec_area,10)函數(shù)解決
# len_x1y1 = rec_po[0].distance_to(rec_po[1])
# a1 = x1*rec_dot[0]/math.pow(len_x1y1,2)+rec_po[0].x
# b1 = y1*rec_dot[0]/math.pow(len_x1y1,2)+rec_po[0].y
# print("{}*{}/{}+{}={}".format(x1,rec_dot[0],math.pow(len_x1y1,2),rec_po[0].x,a1))
# print("{}*{}/{}+{}={}".format(y1,rec_dot[0],math.pow(len_x1y1,2),rec_po[0].y,b1))
len_x1y1 = math.pow(rec_po[0].x-rec_po[1].x,2)+math.pow(rec_po[0].y-rec_po[1].y,2)
a1 = x1*rec_dot[0]/len_x1y1+rec_po[0].x
b1 = y1*rec_dot[0]/len_x1y1+rec_po[0].y
p1 = Point(a1,b1)
a2 = x1*rec_dot[1]/len_x1y1+rec_po[0].x
b2 = y1*rec_dot[1]/len_x1y1+rec_po[0].y
p2 = Point(a2,b2)
x2 = rec_po[2].x - a1
y2 = rec_po[2].y - b1
a3 = x2*rec_height/p1.distance_to(rec_po[2])+a1
b3 = y2*rec_height/p1.distance_to(rec_po[2])+b1
p3 = Point(a3,b3)
a4 = a3+a2-a1
b4 = b3+b2-b1
p4 = Point(a4,b4)
# print("__________{}____________________".format(p1))
# print("__________{}____________________".format(p2))
# print("__________{}____________________".format(p3))
# print("__________{}____________________".format(p4))
rec_po = [p1,p2,p3,p4]
return rec_po
if __name__ == '__main__':
points = []
# for i in range(0, 10):
# points.append(Point(random.randint(1, 10), random.randint(1, 10)))
# 使用算法題中的數(shù)據(jù)，便于驗證
points.append(Point(1.0, 3.00000))
points.append(Point(1, 4.00000))
points.append(Point(2.0000, 1))
points.append(Point(3, 0.0000))
points.append(Point(3.00000, 6))
points.append(Point(6.0, 3.0))
# for each in points:
# print(each)
bot_point, points = get_bottom_point(points)
points = sort_polar_angle_cos(points, bot_point)
# # 拿到了角度排序的值
# for each in points :
# print(each)
# print()
# 拿到凸包集合
con_list = graham_scan(points, bot_point)
# 旋轉卡殼計算面積
rec_area, rec_po = find_min_ret(con_list)
print("rec_area={}".format(rec_area))
for each in rec_po:
print("{}".format(each))注意：
這個對于我這種非ACM的菜雞來說還是費了勁了，寫完仍然存在一些小問題，比如極坐標排序沒有去重，存在一些精度的問題，需要取整函數(shù)的幫助。。。。
python矩形覆蓋問題
題目：
思路：
遞歸,用列表s[]來存儲覆蓋方法的個數(shù)
n=1時，s[0]=1
n=2時，s[1]=2
n=3時，此時分為兩個不重復的覆蓋方法
1+2：s[0]*s[1]
2+1: (s[1]-1)*s[0] %減一是為了不計算重復覆蓋方法
n=4時，分為兩種
1+3:s[0]*s[2]
2+2:(s[1]-1)*s[1]
…
以此類推，可得為n時的覆蓋方法s[n-1]=s[0]*s[-1]+(s[1]-1)*s[-2]
python代碼：
# -*- coding:utf-8 -*-
class Solution:
def rectCover(self, number):
# write code here
l=[1,2]
if number==0:
return 0
while len(l)<number:
t=len(l)
s=l[0]*l[-1]+(l[1]-1)*l[-2]
l.append(s)
return l[number-1]總結
以上為個人經(jīng)驗，希望能給大家一個參考，也希望大家多多支持腳本之家。
相關文章
這篇文章主要介紹了python實現(xiàn)web郵箱掃描的示例(附源碼)，幫助大家更好的理解和學習使用python，感興趣的朋友可以了解下2021-03-03
這篇文章主要介紹了Python中的深拷貝和淺拷貝，通過講解Python中的淺拷貝和深拷貝的概念和背后的原理展開全文，需要的小伙伴可以參考一下2022-07-07
這篇文章主要為大家介紹了python學習探尋WSGI?Application原理詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-04-04
圖像的輪廓檢測不論是機器視覺還是其他方面都有較大作用,下面這篇文章主要給大家介紹了關于如何使用Python?OpenCV提取物體輪廓的相關資料,文中通過實例代碼介紹的非常詳細,需要的朋友可以參考下2022-05-05
由于PDF的文件大多都是只讀文件，有時候為了滿足可以編輯的需要通常可以將PDF文件直接轉換成Word文件進行操作。本文為大家整理了一些實現(xiàn)方法，希望對大家有所幫助2023-02-02
下面小編就為大家分享一篇selenium+python實現(xiàn)自動登錄腳本，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2018-04-04
這篇文章主要介紹了python numpy--數(shù)組的組合和分割實例，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-02-02
python 計算兩個列表的相關系數(shù)的實現(xiàn)
這篇文章主要介紹了python 計算兩個列表的相關系數(shù)的實現(xiàn)，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2019-08-08
這篇文章主要介紹了Python實現(xiàn)的微信支付方式,結合實例形式總結分析了Python實現(xiàn)的三種微信支付方式及相關操作步驟、原理、注意事項,需要的朋友可以參考下2019-04-04
這篇文章主要介紹了Python中的生成器2021-12-12