squarepie解決方案

Question

編程競賽中提出了以下問題，現在已經結束。

Squarepie program

我想最好的解決方案我可以，但總是有時間限制超出錯誤。我的解決方案如下。

首先添加一個結構中的所有邊，首先按長度排序，然後按其位置排序。我有兩個不同的x和y邊緣結構。找到外部矩形，並將其添加到堆棧。現在對於堆棧中的每個矩形，查找是否存在任何交叉邊。如果是通過這個邊將這個矩形分成兩部分並將它們都添加到堆棧中。如果找不到任何平分邊線，請在優先隊列中添加矩形區域。在結束時打印來自優先隊列的元素。

我現在想知道有沒有更快的解決方案。編號： - 附加我的解決方案。

My Final solution

Answer 1

一切看起來除了getLargestRect()，而你也過於複雜不錯。只需返回rectangle(minX, minY, maxX, maxY)即可。您可以在線性時間內找到分鐘數和最大值。當所有行具有相同的長度時，當前實現是O（n ）。

我也編寫了我自己的算法，如果你想看看不同的方法。我的想法是將所有垂直線存儲在一個奇特的數據結構中，然後掃描水平線並找到它們關閉的矩形。

當查看水平線h時，所有具有y1 < h.y && y2 >= h.y的垂直線都按照它們的x值存儲在地圖中。當前水平線形成包含從map[h.x1]到map[h.x2]的所有垂直線的矩形。外部兩行延伸過h.y，但所有中間行必須在h.y處結束，因此在計算矩形區域後將其從地圖中移除。根據它們的y1值，通過對垂直線進行排序，可以高效地找到需要爲每條水平線添加到地圖上的垂直線。

下面是代碼：

#include <iostream> 
#include <map> 
#include <vector> 
#include <algorithm> 

#define min(a, b) ((a) < (b) ? (a) : (b)) 
#define max(a, b) ((a) < (b) ? (b) : (a)) 

using namespace std; 

class Horizontal 
{ 
public: 
    int x1, x2, y; 

    Horizontal(int x1, int x2, int y) : x1(x1), x2(x2), y(y) {} 

    static bool comp(const Horizontal & a, const Horizontal & b) 
    { 
     return a.y < b.y; 
    } 
}; 

class Vertical 
{ 
public: 
    int x, y1; // no need to store y2 

    Vertical(int x, int y1) : x(x), y1(y1) {} 

    static bool comp(const Vertical & a, const Vertical & b) 
    { 
     return a.y1 < b.y1; 
    } 
}; 

long long total = 0; 
int vertI = 0; // index of next vertical to add to currentVerts 
map<int, int> currentVerts; // currentVerts[5] = y1 of the vert line with x=5 
vector<Vertical> verticals; 
vector<Horizontal> horizontals; 
vector<int> solutions; 

void readInput(); 
void processHorizontal(Horizontal & line); 

int main() 
{ 
    cout.precision(10); 

    readInput(); 

    sort(verticals.begin(), verticals.end(), Vertical::comp); 
    sort(horizontals.begin(), horizontals.end(), Horizontal::comp); 

    // process the lines (start at i = 1 to ignore the top one) 
    for (int i = 1; i < horizontals.size(); i++) 
    { 
     processHorizontal(horizontals[i]); 
    } 

    sort(solutions.begin(), solutions.end()); 

    for (int i = solutions.size() - 1; i >= 0; i--) 
    { 
     cout << (double) solutions[i]/total << "\n"; 
    } 
} 

void readInput() 
{ 
    int n; 
    cin >> n; 

    int x1, x2, y1, y2; 

    for (int i = 0; i < n; i++) 
    { 
     cin >> x1 >> y1 >> x2 >> y2; 

     if (x2 < x1) swap(x1, x2); 
     if (y2 < y1) swap(y1, y2); 

     if (x1 == x2) verticals.push_back(Vertical(x1, y1)); 
     else horizontals.push_back(Horizontal(x1, x2, y1)); 
    } 
} 

void processHorizontal(Horizontal & horiz) 
{ 
    // add all vert lines which start above horiz to currentVert 
    for (; vertI < verticals.size() && verticals[vertI].y1 < horiz.y; 
      vertI++) 
    { 
     int x = verticals[vertI].x; 
     currentVerts[x] = verticals[vertI].y1; 
    } 

    map<int, int>::iterator left = currentVerts.find(horiz.x1); 
    map<int, int>::iterator right = currentVerts.find(horiz.x2); 

    map<int, int>::iterator i; 
    map<int, int>::iterator next; 

    for (i = next = left; i != right; i = next) 
    { 
     next++; 

     int width = (*next).first - (*i).first; // difference in x 
     int height = horiz.y - (*i).second; // difference y 
     int area = width * height; 

     total += area; 
     solutions.push_back(area); 

     if (i != left) 
     { 
      // if i is not the start it must be a short 
      // line which ends here, so delete it 
      currentVerts.erase(i); 
     } 
     else 
     { 
      // if it is left, cut the rectangle at horiz.y 
      // by modifying the start of the line 
      (*i).second = horiz.y; 
     } 
    } 
}