首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
您现在的位置: 程式碼之家 >> 編程語言 >  >> C語言 >> C++ >> C++ 入門

LA 4728 Square 解題:多邊形頂點最大距離平方

     編輯:C++ 入門

題目大意

給定多個正方形 (中心座標、邊長、旋轉角度),求所有正方形頂點之間的最大距離平方。

解法

  1. 計算每個正方形的 4 個頂點座標 (旋轉變換)。
  2. 將所有頂點收集為點集。
  3. 套用 旋轉卡殼 求點集凸包直徑平方 (同 POJ 2187)。

核心程式碼


// 旋轉卡殼直徑平方函數 (同 POJ 2187)
int diameter2(vector& points) {
    vector ch = convexHull(points);
    int n = ch.size();
    if (n <= 1) return 0;
    if (n == 2) return dist2(ch[0], ch[1]);
    ch.push_back(ch[0]);
    int ans = 0;
    for (int u=0, v=1; u

正方形頂點計算

正方形中心 (cx, cy),邊長 L,旋轉角 θ。半對角線 d = L / sqrt(2)。四頂點相對中心向量為 (±d, ±d) 旋轉 θ 後加上中心。

  1. 上一篇文章:
  2. 下一篇文章:
Copyright © 程式碼之家 All Rights Reserved