python如何實(shí)現(xiàn)最小矩形覆蓋問題

更新時(shí)間：2023年08月09日 08:51:26 作者：椰子奶糖

這篇文章主要介紹了python如何實(shí)現(xiàn)最小矩形覆蓋問題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教

python實(shí)現(xiàn)最小矩形覆蓋

Description

給定一些點(diǎn)的坐標(biāo)，要求求能夠覆蓋所有點(diǎn)的最小面積的矩形，

輸出所求矩形的面積和四個(gè)頂點(diǎn)坐標(biāo)

Input

第一行為一個(gè)整數(shù)n（3<=n<=50000）

從第2至第n+1行每行有兩個(gè)浮點(diǎn)數(shù)，表示一個(gè)頂點(diǎn)的x和y坐標(biāo)，不用科學(xué)計(jì)數(shù)法

Output

第一行為一個(gè)浮點(diǎn)數(shù)，表示所求矩形的面積（精確到小數(shù)點(diǎn)后5位），

接下來4行每行表示一個(gè)頂點(diǎn)坐標(biāo)，要求第一行為y坐標(biāo)最小的頂點(diǎn)，

其后按逆時(shí)針輸出頂點(diǎn)坐標(biāo).如果用相同y坐標(biāo)，先輸出最小x坐標(biāo)的頂點(diǎn)

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

實(shí)際上它我們py老師布置的小作業(yè)，用py寫

編寫一個(gè)平面二維點(diǎn)集類，要求這個(gè)類的實(shí)例對(duì)象（也就是一個(gè)點(diǎn)）能夠計(jì)算到另一個(gè)點(diǎn)的距離；再編寫一個(gè)函數(shù)，能夠計(jì)算覆蓋一系列點(diǎn)的最小矩形

思路：找到凸包->旋轉(zhuǎn)卡殼->計(jì)算頂點(diǎn)->輸出

建議用編輯器打開，個(gè)人不是很喜歡簡書這里的代碼高亮風(fēng)格

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)
    # 計(jì)算兩點(diǎn)相對(duì)于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))
# 找到極坐標(biāo)系原點(diǎn)
def get_bottom_point(points):
    bot_point = points[0]
    temp = 0
    for i in range(1, len(points)):
        # 找到最左下角的點(diǎn)作為極坐標(biāo)系原點(diǎn)
        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
    # 刪除作為原點(diǎn)的那個(gè)點(diǎn)
    del(points[temp])
    return bot_point, points
# 極坐標(biāo)排序，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掃描法計(jì)算凸包
def graham_scan(points, bot_point):
    # 凸包列表，先加前三個(gè)
    con_list = []
    con_list.append(bot_point)
    con_list.append(points[0])
    con_list.append(points[1])
    # 尋找其他凸包上的點(diǎn)
    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])
    # 最后一個(gè)點(diǎn)也一定在凸包中
    con_list.append(points[-1])
    # # 打印所有凸包點(diǎn)坐標(biāo)
    # 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
        # 最大點(diǎn)積與最小點(diǎn)積
        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
            # 點(diǎn)積求投影長度，同樣存最值？倆？
            # 向量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)
            # 點(diǎn)積
            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ù)計(jì)算頂點(diǎn)坐標(biāo)
    # 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)
# 得到矩形頂點(diǎn)坐標(biāo)
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]))
    # 這么算會(huì)存在精度問題，可用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ù)，便于驗(yàn)證
    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)
    # 旋轉(zhuǎn)卡殼計(jì)算面積
    rec_area, rec_po = find_min_ret(con_list)
    print("rec_area={}".format(rec_area))
    for each in rec_po:
        print("{}".format(each))

注意：

這個(gè)對(duì)于我這種非ACM的菜雞來說還是費(fèi)了勁了，寫完仍然存在一些小問題，比如極坐標(biāo)排序沒有去重，存在一些精度的問題，需要取整函數(shù)的幫助。。。。

python矩形覆蓋問題

題目：

在這里插入圖片描述

思路：

遞歸,用列表s[]來存儲(chǔ)覆蓋方法的個(gè)數(shù)

n=1時(shí)，s[0]=1

n=2時(shí)，s[1]=2

n=3時(shí)，此時(shí)分為兩個(gè)不重復(fù)的覆蓋方法

1+2：s[0]*s[1]

2+1: (s[1]-1)*s[0] %減一是為了不計(jì)算重復(fù)覆蓋方法

n=4時(shí)，分為兩種

1+3:s[0]*s[2]

2+2:(s[1]-1)*s[1]

…

以此類推，可得為n時(shí)的覆蓋方法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]