方形解答

Question

プログラミングコンテストで以下の問題が尋ねられました。

Squarepie program

は、私は私ができる最善の解決策を試してみましたが、常に時間制限がエラーを超えました。私の解決策は以下の通りです。

まず最初に長さでソートされた構造体のすべてのエッジを追加し、次にその位置で追加します。私はxとyの2つの異なる構造を持っていました。外側の矩形を見つけてスタックに追加します。スタック内の各矩形に対して、交差するエッジがあるかどうかを確認します。はいの場合は、この矩形をこの辺で2つに分割し、両方をスタックに追加します。二等辺線を見つけられなかった場合は、矩形の領域を優先度キューに追加します。最後に優先度キューから要素を出力します。

私は今すぐもっと速い解決策があるのだろうか。

編集： - 私のソリューションを添付してください。

My Final solution

Answer 1

すべてはあなたが本当にovercomplicate getLargestRect()、を除いてよさそうです。ちょうどrectangle(minX, minY, maxX, maxY)を返す。最小値と最大値は線形時間で求められます。すべての行の長さが同じ場合、現在の実装はO（n ）です。

別のアプローチを見たい場合は、自分のアルゴリズムをコーディングすることもできます。私の考えは、すべての垂直線を空想的なデータ構造に格納し、次に水平線を走査して、それらが閉じるような長方形を見つけることでした。

水平線hを見ると、y1 < h.y && y2 >= h.yのすべての垂直線は、そのx値によってマップに格納されます。現在の水平線は、すべての垂直線がmap[h.x1]からmap[h.x2]までの長方形を形成します。外側の2つの線は、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; 
     } 
    } 
}