USACO 5.2.2 Electric Fences 电网 fence3
一道搜索题，也与计算几何联系。当供电点固定后，计算电网的总长度并不难，这道题的核心任务就在于找到这个点。（有人说可以用“数学方法”直接找到，我不会）
对于查找这个点，采用一般的搜索是会超时的。我采用了“局部搜索”的方法。就是先以一个较大的距离网格扫描，找到目前使结果最短的点的坐标。最终结果一定在目前找到的点的附近，然后对这个范围进行细化的搜索，直到找到要求的精度为止。
对于这道题，精度要求不高，搜索两次就行了。因为只要保留一位小数，所以我把所有读入的点都乘以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