キューがうまくはたらきません

Question

前提・実現したいこと

コッホ曲線(フラクタル図形を求める問題)をキューを用いて解こうとしているのですが、n=2以降うまく働かず困っております。どなたか解決策を教えていただきたいです。

該当のソースコード

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>

using namespace std;

queue<pair<long double, long double> > p;
const long double h = sqrt(3)/2.0;

void fractale(){
    pair<long double, long double> l, r, temp;
    do {
        l = p.front(); p.pop();
        r = p.front(); p.pop();
        long double theta = atan2(r.second-l.second, r.first-l.first);
        long double leng = sqrt((r.second-l.second)*(r.second-l.second)+(r.first-l.first)*(r.first-l.first));
        p.push(l);
        temp = make_pair(l.first+(r.first-l.first)/3.0, l.second+(r.second-l.second)/3.0);
        p.push(temp);
        p.push(temp);
        temp = make_pair(l.first+(r.first-l.first)/2.0+leng*h*sin(theta)/3.0, l.second+(r.second-l.second)/2.0+leng*h*cos(theta)/3.0);
        p.push(temp);
        p.push(temp);
        temp = make_pair(l.first+2*(r.first-l.first)/3.0, l.second+2*(r.second-l.second)/3.0);
        p.push(temp);
        p.push(temp);
        p.push(r);
    } while (r.first != 100);
}

int main(){
    int n;
    cin >> n;
    pair<long double, long double> temp = make_pair(0.0, 0.0);
    p.push(temp);
    temp = make_pair(100.0, 0.0);
    p.push(temp);
    for (int i = 0; i < n; i++){
        fractale();
    }
    cout << fixed << setprecision(10);
    cout << p.front().first << " " << p.front().second << endl;
    p.pop();
    do {
        cout << p.front().first << " " << p.front().second << endl;
    	p.pop(); p.pop();
    } while (p.front().first != 100);
    cout << p.front().first << " " << p.front().second << endl;
}

試したこと

回答ありがとうございます。ご指摘の内容をもとに改善したのですが、今度は動作しないようになってしまいました。n>=1の入力を仮定しているので、pop()の部分は問題ないと思うのですが、なぜ動かないかわかりません。

Comments

[y_waiwai]

うまく働かないとはどういう動作をするんでしょうか

[Magolors]

n=2で
66.6666666667 0.0000000000
50.0000000000 -28.8675134595
33.3333333333 0.0000000000
0.0000000000 0.0000000000
11.1111111111 0.0000000000
12.9629629630 3.2075014955
16.6666666667 6.4150029910
14.8148148148 6.4150029910
16.6666666667 9.6225044865
22.2222222222 0.0000000000
25.9259259259 0.0000000000
27.7777777778 3.2075014955
29.6296296296 0.0000000000
33.3333333333 0.0000000000
50.0000000000 28.8675134595
51.8518518519 25.6600119640
50.0000000000 25.6600119640
53.7037037037 22.4525104685
55.5555555556 19.2450089730
50.0000000000 19.2450089730
53.7037037037 16.0375074775
52.7777777778 17.6412582252
57.4074074074 12.8300059820
61.1111111111 9.6225044865
66.6666666667 0.0000000000
77.7777777778 0.0000000000
83.3333333333 9.6225044865
88.8888888889 0.0000000000
100.0000000000 0.0000000000

と異なる解を示してしまいます。

[y_waiwai]

うまく働いた場合はどういう解を示すんでしょう。
それらを、質問文を編集して、質問に追記しましょう

[Magolors]

すみませんでした。追加いたしました。

Answer 1

        l = p.front(); p.pop();//辺の左端
        r = p.front(); p.pop();//辺の右端

ここで右端もpopしてますが、右端の点は次の左端となるべき点です。
ここで取り出してはいけません。

Answer 2

ざっくり見た感じですが, fractale の do-while 内では始点終点の2つを"直線"として取り出しているのですから, 計算の結果は4本の"直線"の各始点終点である計8つの点を入れないといけないのではないでしょうか.

編集1

表示が面倒になってしまうようですので, yudedako67 さんの回答のようにキューに各座標を1つだけ入れる形で再帰のコードにしてみました.
c++ は大分前に勉強したのみですのでコードの質はご容赦ください.
一応 paiza.io で実行は確認しましたが, 表示される値が一部変なので, 計算式に問題はあるかと思います.

編集2

テスト用にコードを修正しました.

#include <iostream>
#include <queue>
#include <cmath>
#include <iomanip>
#include <bits/stdc++.h>

using namespace std;

const long double H = sqrt(3)/2.0;

void fractal(queue<pair<double, double>>& q, int n) {
    if(n <= 0) return;

    pair<double, double> l, r, t;
    int size = q.size();
    for(int i=0; i<size-1; i++) {
        l = q.front(); q.pop();
        r = q.front();
        
        double w = r.first - l.first;
        double h = r.second - l.second;
        double theta = atan2(h, w);
        double length = sqrt(h*h + w*w);

        q.push(l);
        t = make_pair(l.first+w/3.0, l.second+h/3.0);
        q.push(t);
        t = make_pair(l.first+w/2.0+length*H*sin(theta)/3.0, l.second+h/2.0+length*H*cos(theta)/3.0); //orig
        //t = make_pair(t.first+length*cos(theta+M_PI/3.0)/3.0, t.second+length*sin(theta+M_PI/3.0)/3.0);
        q.push(t);
        t = make_pair(l.first+2*w/3.0, l.second+2*h/3.0);
        q.push(t);
    }
    r = q.front(); q.pop();
    q.push(r);

    fractal(q, --n);
}
void test(int n, const char* ex) {
    cout << "test: n=" << n << endl;

    queue<pair<double, double>> q;
    q.push(make_pair(0.0, 0.0));
    q.push(make_pair(100.0, 0.0));

    fractal(q, n);

    ostringstream oss;
    oss << fixed << setprecision(8);
    for (; !q.empty(); q.pop()){
        oss << q.front().first << " " << q.front().second << "\n";
    }

    if(string(ex).compare(oss.str()) == 0) {
        cout << "=== OK ===" << endl;
    } else {
        cout << "*** NG ***" << endl;
        cout << oss.str() << flush;
    }
}
int main(){
    test(1,
        "0.00000000 0.00000000\n"
        "33.33333333 0.00000000\n"
        "50.00000000 28.86751346\n"
        "66.66666667 0.00000000\n"
        "100.00000000 0.00000000\n");

    test(2,
        "0.00000000 0.00000000\n"
        "11.11111111 0.00000000\n"
        "16.66666667 9.62250449\n"
        "22.22222222 0.00000000\n"
        "33.33333333 0.00000000\n"
        "38.88888889 9.62250449\n"
        "33.33333333 19.24500897\n"
        "44.44444444 19.24500897\n"
        "50.00000000 28.86751346\n"
        "55.55555556 19.24500897\n"
        "66.66666667 19.24500897\n"
        "61.11111111 9.62250449\n"
        "66.66666667 0.00000000\n"
        "77.77777778 0.00000000\n"
        "83.33333333 9.62250449\n"
        "88.88888889 0.00000000\n"
        "100.00000000 0.00000000\n");
}