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.
    
    Your program ('fence3') produced all correct answers!  This is your
    submission #20 for this problem.  Congratulations!
    
    
/*
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;
}

相關日誌