傳送門

文章目錄

• 題意：
• 思路：

題意：

給你一顆$n$個(gè)點(diǎn)的樹，讓你在二維平面中構(gòu)造一顆樹，保證相鄰點(diǎn)的距離正好為$1$，并且線段不能有相交，坐標(biāo)絕對值$\le 3e3$。

$n\le 1e3$

思路：

其實(shí)樣例已經(jīng)給了提示了，當(dāng)時(shí)光聽隊(duì)友說了句是菊花圖，也就沒多看，其實(shí)要是把第一個(gè)樣例怎么來的搞明白我感覺這個(gè)題就有了。

不按照題解的想法，我們考慮以$(0,0)$為原點(diǎn)，讓后將第一、二象限分成$n?1$條直線，我們只需要在$dfs$的過程中依次從小到大選擇相應(yīng)斜率的直線即可，這樣保證了線不相交，考慮怎么保證距離為$1$呢？根據(jù)初中知識可知，${\sin }^{2}a+{\cos }^{2}b=1$，所以對于$u$的下一個(gè)點(diǎn)$v$，對應(yīng)的$(x,y)$應(yīng)該是$(x_u+\cos (ang),y_u+\sin (ang))$，其中$ang$是對應(yīng)的角度。

所以這個(gè)題就完事啦。

// Problem: C - Circuit Board Design // Contest: Virtual Judge - Namomo Summer Camp Day 4 // URL: https://vjudge.net/contest/455214#problem/C // Memory Limit: 262 MB // Time Limit: 1000 ms // // Powered by CP Editor (https://cpeditor.org)//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native") //#pragma GCC optimize(2) #include<cstdio> #include<iostream> #include<string> #include<cstring> #include<map> #include<cmath> #include<cctype> #include<vector> #include<set> #include<queue> #include<algorithm> #include<sstream> #include<ctime> #include<cstdlib> #include<random> #include<cassert> #define pb push_back using namespace std;typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> PII;const int N=1010,mod=1e9+7,INF=0x3f3f3f3f; const double eps=1e-6,PI=acos(-1);int n; vector<int>v[N]; double x[N],y[N]; int cnt;void dfs(int u,int fa) {for(auto xx:v[u]) {if(xx==fa) continue;double reg=cnt/(n-1.0)*PI;x[xx]=x[u]+cos(reg);y[xx]=y[u]+sin(reg);cnt++;dfs(xx,u);} }int main() { // ios::sync_with_stdio(false); // cin.tie(0);scanf("%d",&n);for(int i=1;i<=n-1;i++) {int a,b; scanf("%d%d",&a,&b);v[a].pb(b); v[b].pb(a);}dfs(1,0);for(int i=1;i<=n;i++) printf("%.10lf %.10lf\n",x[i],y[i]);return 0; } /**/ 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的NWERC 2018 C. Circuit Board Design 树 + 构造的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。