uva10012 はあなたが思っているほど単純ではありません

初めてこの質問をしたとき、最初のアイデアは、すべての円を配置し、前の円に接するように新しい円を配置し、最終的に最小サイズを取得することでした。バックトラッキングによる長方形の。 10 分以上編集した後、結果は WA になりました。しばらく考えた後、問題は前の円に接しているだけではいけないことがわかりました (最初の円の半径が非常に大きい場合)。 、100、2 番目の円は非常に小さい、半径は 1、3 番目の円も非常に大きく、半径も 100 です。3 番目の円を配置するとき、2 番目の円に接していれば、間違いなく最初の円と交差することは許可されていません)。それからコードを修正し始めたところ、さまざまなエラーが発生し、断続的に一晩中、朝中ずっと作業を続けました。

最初に考えるべきことは、円を配置するたびに、まず前に配置した円に接するようにし、次に、前に配置した円と交差するかどうかを判断し、交差しない場合は決定する必要があるということです。 、これは、これを置くことが正しく、最も距離を節約することを意味します。任意の円がそれと交差する場合、それは前の円に接することができないことを意味します。次に、別の円を前に押して前の円に接するようにします。円が他の円に接しているかどうかを判断します。 。 。それらが交差するかどうかを判断するために、各円の中心位置を格納するために center 配列が追加されます。ここまでの考え方は非常に正しく明確でしたが、そこで3つの「和」のポイントに出会いました。

WA1: 長方形の最小サイズを判断する場合、最後の円の右端の位置は使用できません。最後の円は非常に小さい可能性があり、その右端の位置は長方形の右端の位置ほど適切ではないためです。前の円の辺の位置が遠いので、代わりに各円の中心位置+半径の最大値が長方形の最小サイズとして決定されます。

WA2: 最初のいくつかの円を配置するときは、円の中心位置、つまり円の半径が 0 未満にならないように注意してください。たとえば、最初の円の半径が 1 で、2 番目の要素の半径が 100 の場合、2 番目の要素を配置しても、円の左側が長方形のボックスの壁を超えるため、最初の円に接することができません。 ！

WA3: main 関数の MinL 設定が小さすぎます。テスト データの数が非常に多いと推定されます。初期設定は 65536 です。その結果、WA は DBL_MAX に変更され、AC が達成されます。 ！

#include#include#include#include#includeusing namespace std;  
  
int m,Put[10];          //Put[i]:放置的第i个圆的编号  
double MinL,size[10],center[10];//size[i]:编号为i的圆的半径；center[i]:放置的第i个圆的圆心位置  
bool vis[10];  
  
double getlen(int a,int b)      //计算两圆心间的距离  
{  
    return sqrt((size[a]+size[b])*(size[a]+size[b])-(size[a]-size[b])*(size[a]-size[b]));  
}  
bool isok(int a,int b)          //是否和之前放的圆相交  
{  
    for (int i=0;i<b;i++)  
    {  
        if (sqrt((center[i]-center[a])*(center[i]-center[a])+(size[Put[i]]-size[Put[a]])*(size[Put[i]]-size[Put[a]]))<(size[Put[i]]+size[Put[a]]))  
            return false;  
    }  
    return true;  
}  
void dfs(int cur)  
{  
    int i,j;  
    if (cur==m)  
    {     
        double maxsize=0;  
        for (int k=0;kmaxsize)  
                maxsize=center[k]+size[Put[k]];  
        }  
        if (maxsize<MinL)  
            MinL=maxsize;  
    }  
    else  
    {  
        for (i=0;i=0;j--)  
                {  
                    tmpl=getlen(Put[j],i);  
                    center[cur]=center[j]+tmpl;  
                    if (center[cur]-size[Put[cur]]>n;  
    while(n--)  
    {  
        cin>>m;  
        MinL=DBL_MAX;  
        memset(vis,0,sizeof(vis));  
        for (int i=0;i>size[i];  
        for (int i=0;i<m;i++)  
        {  
            Put[0]=i;  
            center[0]=size[i];  
            vis[i]=1;  
            dfs(1);  
            vis[i]=0;  
        }  
        cout<<fixed<<setprecision(3)<<MinL<<endl;  
    }  
    return 0;  
}

[関連チュートリアルの推奨事項]

1. 入門からマスターまでの PHP プログラミングに関する完全なビデオチュートリアル

2. 🎜>初心者からマスターまでの php

3.

ブートストラップ チュートリアル