USACO 5.2.2 Electric Fences 電網 fence3
本文正體字版由OpenCC轉換
一道搜索題，也與計算幾何聯繫。當供電點固定後，計算電網的總長度並不難，這道題的核心任務就在於找到這個點。（有人說可以用“數學方法”直接找到，我不會）
對於查找這個點，採用一般的搜索是會超時的。我採用了“局部搜索”的方法。就是先以一個較大的距離網格掃描，找到目前使結果最短的點的座標。最終結果一定在目前找到的點的附近，然後對這個範圍進行細化的搜索，直到找到要求的精度爲止。
對於這道題，精度要求不高，搜索兩次就行了。因爲只要保留一位小數，所以我把所有讀入的點都乘以10，當作整數點處理。第一次搜索的精度的確定直接影響到是否能過測試數據。在我的程序中，用sec表示第一次網格搜索的寬度。sec的選取很影響程序效率。我做了一個測試。
sec=10
Test 11: TEST OK [0.886 secs, 2844 KB]
> Run 12: Execution error: Your program (`fence3') used more than
the allotted runtime of 1 seconds (it ended or was stopped at
1.145 seconds) when presented with test case 12. It used 2840 KB
of memory.
sec=20
Test 11: TEST OK [0.454 secs, 2844 KB]
Test 12: TEST OK [0.583 secs, 2840 KB]
sec=30
Test 11: TEST OK [0.335 secs, 2840 KB]
Test 12: TEST OK [0.432 secs, 2840 KB]
sec=40
Test 11: TEST OK [0.270 secs, 2840 KB]
Test 12: TEST OK [0.356 secs, 2840 KB]
sec=50
Test 11: TEST OK [0.281 secs, 2844 KB]
Test 12: TEST OK [0.335 secs, 2844 KB]
sec=60
Test 11: TEST OK [0.270 secs, 2840 KB]
Test 12: TEST OK [0.356 secs, 2844 KB]
sec=70
Test 11: TEST OK [0.313 secs, 2844 KB]
Test 12: TEST OK [0.389 secs, 2840 KB]
sec=80
Test 11: TEST OK [0.346 secs, 2840 KB]
Test 12: TEST OK [0.432 secs, 2840 KB]
sec=90
Test 11: TEST OK [0.378 secs, 2844 KB]
Test 12: TEST OK [0.486 secs, 2840 KB]
sec=100
Test 11: TEST OK [0.443 secs, 2844 KB]
Test 12: TEST OK [0.562 secs, 2844 KB]
sec=150
Test 11: TEST OK [0.853 secs, 2844 KB]
> Run 12: Execution error: Your program (`fence3') used more than
the allotted runtime of 1 seconds (it ended or was stopped at
1.069 seconds) when presented with test case 12. It used 2840 KB
of memory.
可以發現，sec取得太小仍然過不了。sec=20的時候剛好通過。當sec=50，效率是最高的。sec大於50時，效率又開始下降。當sec=150，又過不了了。
USER: CmYkRgB123 CmYkRgB123 [cmykrgb1]
TASK: fence3
LANG: C++
Compiling...
Compile: OK
Executing...
Test 1: TEST OK [0.011 secs, 2840 KB]
Test 2: TEST OK [0.011 secs, 2840 KB]
Test 3: TEST OK [0.032 secs, 2840 KB]
Test 4: TEST OK [0.043 secs, 2840 KB]
Test 5: TEST OK [0.130 secs, 2844 KB]
Test 6: TEST OK [0.119 secs, 2844 KB]
Test 7: TEST OK [0.227 secs, 2840 KB]
Test 8: TEST OK [0.238 secs, 2844 KB]
Test 9: TEST OK [0.292 secs, 2844 KB]
Test 10: TEST OK [0.248 secs, 2844 KB]
Test 11: TEST OK [0.270 secs, 2844 KB]
Test 12: TEST OK [0.335 secs, 2844 KB]
All tests OK.
</span>
<span>Your program ('fence3') produced all correct answers! This is your
submission #20 for this problem. <strong>Congratulations!</strong>
</span>
</pre>
/*
ID: cmykrgb1
PROG: fence3
LANG: C++
*/
#include <iostream>
#include <fstream>
#include <cmath>
#define MAXN 151
#define sec 50
#define INF 0x7FFFFFFF
using namespace std;
typedef struct
{
int x1,x2,y1,y2;
}line;
ifstream fi("fence3.in");
FILE *fo=fopen("fence3.out","w");
line L[MAXN];
line mp;
int ansx,ansy,N;
double anst;
void swap(int &x,int &y)
{
int z=x;
x=y;
y=z;
}
void init()
{
int i;
mp.x1=mp.y1=INF;
anst=INF;
fi >> N;
for (i=1;i<=N;i++)
{
fi >> L[i].x1 >> L[i].y1 >> L[i].x2 >> L[i].y2;
L[i].x1*=10; L[i].x2*=10; L[i].y1*=10; L[i].y2*=10;
if (L[i].x1>L[i].x2) swap(L[i].x1,L[i].x2);
if (L[i].y1>L[i].y2) swap(L[i].y1,L[i].y2);
if (L[i].x1<mp.x1) mp.x1=L[i].x1;
if (L[i].y1<mp.y1) mp.y1=L[i].y1;
if (L[i].x2>mp.x2) mp.x2=L[i].x2;
if (L[i].y2>mp.y2) mp.y2=L[i].y2;
}
}
inline double dis(int x1,int y1,int x2,int y2)
{
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
double count(int x,int y)
{
double d=0;
int i;
for (i=1;i<=N;i++)
{
if (L[i].y1==L[i].y2) //平行於x軸
{
if (x>=L[i].x1 && x<=L[i].x2) //垂線
d+=abs(y-L[i].y1);
else if (x<=L[i].x1)
d+=dis(x,y,L[i].x1,L[i].y1); //左斜線
else
d+=dis(x,y,L[i].x2,L[i].y2); //右斜線
}
else //平行於y軸
{
if (y>=L[i].y1 && y<=L[i].y2) //垂線
d+=abs(x-L[i].x1);
else if (y<L[i].y1)
d+=dis(x,y,L[i].x1,L[i].y1); //下斜線
else
d+=dis(x,y,L[i].x2,L[i].y2); //上斜線
}
}
return d;
}
void search()
{
int i,j,px,py;
double dist;
for (i=mp.x1;i<=mp.x2;i+=sec) //第一遍掃描
{
for (j=mp.y1;j<=mp.y2;j++)
{
dist=count(i,j);
if (dist<anst)
{
anst=dist;
px=i;
py=j;
}
}
}
for (i=px-sec;i<=px+sec;i++) //第二遍掃描
{
for (j=py-sec;j<=py+sec;j++)
{
dist=count(i,j);
if (dist<=anst)
{
anst=dist;
ansx=i;
ansy=j;
}
}
}
}
void print()
{
double ax,ay;
ax=ansx/10.0;
ay=ansy/10.0;
anst/=10.0;
fprintf(fo,"%.1lf %.1lf %.1lfn",ax,ay,anst);
fclose(fo);
fi.close();
}
int main()
{
init();
search();
print();
return 0;
}
上次修改時間 2017-05-22