Beyond the Void
BYVoid
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

相關日誌