無人機航線規劃
非最短非最長,因為只有10個點,直接搜
標題:無人機航線規劃
某海島遭遇颶風災害,道路設施受損嚴重。救援部門為盡快探明主要交通干道的受損情況,在地圖上劃定了主要交通干道的偵察點,
(如圖a所示),決定使用無人機對這些偵察點進行偵察。救援部門想知道,在只有一架無人機,且無人機有航程限制的情況下,考慮
無人機的返航,如何規劃無人機的航線(如圖b所示),才能對更多的偵察點進行偵察。
給出無人機的起點0的坐標(x0,y0),偵察點的數量n, 無人機的航程m,以及各偵察點i的坐標(xi,yi)。
請輸出覆蓋最多偵察點的路徑中航程最短的路徑。若路徑有多個,輸出字典序最大的路徑。
計算距離時請保留到小數點后兩位。
【輸入格式】
n m
x0 y0
x1 y1
x2 y2
. . .
xn yn
對于40%的數據,0<n<5;
對于70%的數據,0<n<7;
對于100%的數據, 0<n<10; 10<m<100; -10 <= xi, yi <= 10 ;
【輸出格式】
輸出無人機的偵察航線
【輸入樣例1】
5 35
4 1
2 7
7 1
0 8
-3 -3
3 6
【輸出樣例1】
0->4->3->1->5->2->0
【輸入樣例2】
10 45
0 0
9 -6
-2 -5
9 1
9 9
6 0
-8 -7
4 -2
10 7
-6 2
-3 6
【輸出樣例2】
0->9->10->4->8->3->5->7->0
資源約定:
峰值內存消耗(含虛擬機) < 256M
CPU消耗 < 2000ms
請嚴格按要求輸出,不要畫蛇添足地打印類似:“請您輸入…” 的多余內容。
所有代碼放在同一個源文件中,調試通過后,拷貝提交該源碼。
不要使用package語句。不要使用jdk1.7及以上版本的特性。
主類的名字必須是:Main,否則按無效代碼處理。
錯誤10%是因為這個。。我不改。明明說了輸出字典序最大的路徑,哪里錯了。。倒過來
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
const double FIG=1e-2;
int n,fnum=0,pt[15],fpt[15];
bool f[15];
double m,fm=0,x[15],y[15],dis[15][15];
void Try(int num,int pos,double nowm)
{
bool flag=0;
for(int i=n;i>0;i--)
{
if(!f[i]&&m-(dis[i][pos]+nowm+dis[i][0])>=FIG)
{
pt[num+1]=i;
f[i]=1;
Try(num+1,i,nowm+dis[i][pos]);
f[i]=0;
flag=1;
}
}
if(!flag)
{
if(num>fnum||num==fnum&&fm-(nowm+dis[pos][0])>FIG)
{
fnum=num;
fm=nowm+dis[pos][0];
for(int i=1;i<=num;i++)
{
fpt[i]=pt[i];
}
}
}
}
int main()
{
scanf("%d%lf",&n,&m);
for(int i=0;i<=n;i++)
{
scanf("%lf%lf",&x[i],&y[i]);
for(int j=0;j<i;j++)
{
dis[i][j]=dis[j][i]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
}
if(i)fm+=dis[i][i-1];
}
if(m-fm>=FIG)fnum=n;
Try(0,0,0);
for(int i=0;i<=fnum;i++)
{
printf("%d->",fpt[i]);
}
printf("0\n");
return 0;
}
智能推薦
Linux C系統編程-線程互斥鎖(四)
互斥鎖 互斥鎖也是屬于線程之間處理同步互斥方式,有上鎖/解鎖兩種狀態。 互斥鎖函數接口 1)初始化互斥鎖 pthread_mutex_init() man 3 pthread_mutex_init (找不到的情況下首先 sudo apt-get install glibc-doc sudo apt-get install manpages-posix-dev) 動態初始化 int pthread_...
統計學習方法 - 樸素貝葉斯
引入問題:一機器在良好狀態生產合格產品幾率是 90%,在故障狀態生產合格產品幾率是 30%,機器良好的概率是 75%。若一日第一件產品是合格品,那么此日機器良好的概率是多少。 貝葉斯模型 生成模型與判別模型 判別模型,即要判斷這個東西到底是哪一類,也就是要求y,那就用給定的x去預測。 生成模型,是要生成一個模型,那就是誰根據什么生成了模型,誰就是類別y,根據的內容就是x 以上述例子,判斷一個生產出...
styled-components —— React 中的 CSS 最佳實踐
https://zhuanlan.zhihu.com/p/29344146 Styled-components 是目前 React 樣式方案中最受關注的一種,它既具備了 css-in-js 的模塊化與參數化優點,又完全使用CSS的書寫習慣,不會引起額外的學習成本。本文是 styled-components 作者之一 Max Stoiber 所寫,首先總結了前端組件化樣式中的最佳實踐原則,然后在此基...
猜你喜歡
19.vue中封裝echarts組件
19.vue中封裝echarts組件 1.效果圖 2.echarts組件 3.使用組件 按照組件格式整理好數據格式 傳入組件 home.vue 4.接口返回數據格式...
【一只蒟蒻的刷題歷程】【藍橋杯】歷屆試題 九宮重排 (八數碼問題:BFS+集合set)
資源限制 時間限制:1.0s 內存限制:256.0MB 問題描述 如下面第一個圖的九宮格中,放著 1~8 的數字卡片,還有一個格子空著。與空格子相鄰的格子中的卡片可以移動到空格中。經過若干次移動,可以形成第二個圖所示的局面。 我們把第一個圖的局面記為:12345678. 把第二個圖的局面記為:123.46758 顯然是按從上到下,從左到右的順序記錄數字,空格記為句點。 本題目的任務是已知九宮的初態...
dataV組件容器寬高發生變化后,組件不會自適應解決方法
項目中需要大屏幕數據展示,于是使用了dataV組件,但是使用是發現拖動瀏覽器邊框,dataV組件顯示異常,如圖: 于是查了官網,官網的解釋如下: 于是按照官網的意思編寫代碼: 于是可以自適應了...
CSS3干貨10:如何做一個板塊標題水平線左邊帶顏色效果
很多網站在設計欄目標題的時候,喜歡用下劃線分開欄目標題和內容部分。 而且線條左邊的部分往往還有顏色,且這個顏色跟標題的文字長短保持一致。效果如圖所示: 這種效果其實很簡單。 我這里給大家推薦兩種方式: 假定我們的標題部分 HTML 結構如下: 方式一:利用下邊框。灰色部分是 h1 的下邊框,藍色部分是 span 標簽的下邊框。 h1 的高度為 40px,span 也設置它的高度為 40px。這樣,...