NOI 2003 衛星探測

這道題我的方法是二分判斷+計算幾何。

首先要找到多邊形的邊界,可以用四個點分別表示多邊形上下左右邊界的一個頂點。尋找邊界可以用二分的方法。由於已知原點一定在多邊形內或邊上,尋找左邊界就可以從x取值-10000到0之間二分答案,其餘邊界以此類推。

確定邊界後,接着要確定每個每個頂點的位置,由於這是一個凸多邊形,而且沒有邊與座標軸平行,所以從左界點到下界點之間的一段折線斜率一定是嚴格單調遞增的,類似的相鄰兩個邊界點之間的一段折線的斜率也都是單調的。於是我們可以二分答案,確定折線每條線段的端點。最後在按照極角排序好的頂點順序求出多邊形面積,順序輸出每個頂點座標。其實再寫程序時如果求折線端點的順序恰當,頂點就是直接排好的。

爲了儘量減少詢問次數,可以把已經詢問過的記錄下來,以免重複詢問。計算幾何題一般來說細節較多,代碼量大,很難一次寫對。再加上這是一個交互式題,我調了好長時間。由於詢問次數的限制,我的程序不能拿到滿分,後面有幾個點都是8分9分。誰要是能寫出滿分的程序,我一定拜讀。

/* 
 * Problem: NOI2003 detect
 * Author: Guo Jiabao
 * Time: 2009.5.26 13:30
 * State: Solved
 * Memo: 交互式 二分 凸多邊形面積
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include "detect_lib.h"
using namespace std;
const int MAXB=10000,MAXL=20001,MAXN=201;
const double zero=1e-6;
struct point
{
    double x,y;
}LB,RB,BB,TB,V[MAXN],V2[MAXN];
struct ask
{
    int acnt;
    double v1,v2;
}AX0[MAXL],AY0[MAXL],*Ax,*Ay;
int N,N2;
double (*opt)(double,double) ;
double min(double a,double b)
{
    if (a==MAXB+1) return b;
    if (b==MAXB+1) return a;
    return a<b?a:b;
}
double max(double a,double b)
{
    if (a==MAXB+1) return b;
    if (b==MAXB+1) return a;
    return a>b?a:b;
}
void init()
{
    Ax=AX0+MAXB; Ay=AY0+MAXB;
    prog_initialize();
    for (int i=-MAXB;i<=MAXB;i++)
        Ax[i].acnt=Ay[i].acnt=-1;
}
ask Ask(int k,bool x)
{
    if (x)
    {
        if (Ax[k].acnt==-1)
            Ax[k].acnt=ask_x(k, &Ax[k].v1, &Ax[k].v2);
        if (Ax[k].acnt==1)
            Ax[k].v2=MAXB+1;
        return Ax[k];
    }
    else
    {
        if (Ay[k].acnt==-1)
            Ay[k].acnt=ask_y(k, &Ay[k].v1, &Ay[k].v2);
        if (Ay[k].acnt==1)
            Ay[k].v2=MAXB+1;
        return Ay[k];
    }
}
int BS_inc(int a,int b,bool x)
{
    int m;ask A;
    while (a<=b)
    {
        m=(a+b)>>1;
        A=Ask(m,x);
        if (A.acnt==0)
            a=m+1;
        else if (A.acnt==2)
            b=m-1;
        else
            return m;
    }
}
int BS_dec(int a,int b,bool x)
{
    int m;ask A;
    while (a<=b)
    {
        m=(a+b)>>1;
        A=Ask(m,x);
        if (A.acnt==0)
            b=m-1;
        else if (A.acnt==2)
            a=m+1;
        else
            return m;
    }
}
void Boundary()
{
    LB.y=Ax[ (int)(LB.x=BS_inc(-MAXB,0,true)) ].v1;
    BB.x=Ay[ (int)(BB.y=BS_inc(-MAXB,0,false))].v1;
    RB.y=Ax[ (int)(RB.x=BS_dec(0,MAXB,true))  ].v1;
    TB.x=Ay[ (int)(TB.y=BS_dec(0,MAXB,false)) ].v1;
}
double FP(point p1,point p2)
{
    return (p1.x * p2.y)-(p2.x * p1.y);
}
inline bool online(point p1,point p2,point p3,point p4)
{
    point r1,r2;
    r1.x=p1.x-p2.x; r1.y=p1.y-p2.y;
    r2.x=p3.x-p4.x; r2.y=p3.y-p4.y;
    return fabs(FP(r1,r2))<zero;
}
bool check(int p,int m)
{
    point p1,p2,r1,r2;
    ask A;
    r1.x=p; r2.x=p+1;
    A=Ask(p,true);
    r1.y=opt(A.v1,A.v2);
    A=Ask(p+1,true);
    r2.y=opt(A.v1,A.v2);
    p1.x=m; p2.x=m+1;
    A=Ask(m,true);
    p1.y=opt(A.v1,A.v2);
    A=Ask(m+1,true);
    p2.y=opt(A.v1,A.v2);
    return !online(r1,r2,p1,p2);
}
int BS(int a,int b,int p)
{
    int m;
    if (a>b || !check(p,b))
        return MAXB+1;
    while (a+1<b)
    {
        m=(a+b)>>1;
        if (check(p,m))
            b=m;
        else
            a=m+1;
    }
    if (check(p,a))
        b=a;
    return b;
}
void Vertex()
{
    int x,x1;
    V[++N]=LB;
    opt=min;
    for (x=LB.x;x<BB.x;x=x1)
    {
        x1=BS(x+1,BB.x-1,x);
        if (x1==MAXB+1) break;
        V[++N].x=x1;
        V[N].y=opt(Ax[x1].v1,Ax[x1].v2);
    }
    if (BB.x!=LB.x || BB.y!=LB.y)
        V[++N]=BB;
    for (x=BB.x;x<RB.x;x=x1)
    {
        x1=BS(x+1,RB.x-1,x);
        if (x1==MAXB+1) break;
        V[++N].x=x1;
        V[N].y=opt(Ax[x1].v1,Ax[x1].v2);
    }
    opt=max;
    for (x=LB.x;x<TB.x;x=x1)
    {
        x1=BS(x+1,TB.x-1,x);
        if (x1==MAXB+1) break;
        V2[++N2].x=x1;
        V2[N2].y=opt(Ax[x1].v1,Ax[x1].v2);
    }
    if (TB.x!=LB.x || TB.y!=LB.y)
        V2[++N2]=TB;
    for (x=TB.x;x<RB.x;x=x1)
    {
        x1=BS(x+1,RB.x-1,x);
        if (x1==MAXB+1) break;
        V2[++N2].x=x1;
        V2[N2].y=opt(Ax[x1].v1,Ax[x1].v2);
    }
    if ((BB.x!=RB.x || BB.y!=RB.y)&&(TB.x!=RB.x || TB.y!=RB.y))
        V2[++N2]=RB;
    for (;N2>=1;N2--)
        V[++N]=V2[N2];
}
void Square()
{
    int i;
    double S=0,k;
    for (i=1;i<N;i++)
    {
        k=FP(V[i],V[i+1]);
        if (k<0) k=-k;
        S+=k;
    }
    k=FP(V[N],V[1]);
    if (k<0) k=-k;
    S+=k;
    S/=2;
    ret_area(S);
}
void solve()
{
    Boundary();
    Vertex();
    Square();
    ret_n(N);
    for (int i=1;i<=N;i++)
        ret_vertex(V[i].x,V[i].y);
}
int main()
{
    init();
    solve();
    return 0;
}
<h2><span class="mw-headline">衛星探測 </span></h2>

【問題描述】

A國最近檢測到了B國內有不正常的輻射,經調查發現,這是因爲B國正在耗資百億研製新式武器——連環陣。可是,由於B國對此武器的高度保密 措施,A國的間諜甚至無法確定出連環陣的具體位置。不過,A國的衛星還是可以找出連環陣所在的基地的。我們現在知道該基地是一個邊上含有放射性物質的凸多 邊形。經研究發現,在這個凸多邊形所在的平面內,它具有如下性質:
  • 包含座標原點;
  • 任意兩條邊不在同一直線上;
  • 沒有和x軸或y軸平行的邊;
  • 所有頂點的x座標和y座標都是整數。

    現在A國可以通過衛星發出無限大的扇形探測波,與該凸多邊形所在平面交於一條直線。不過該直線不是與x軸平行,就是與y軸平行。通過反射信號,我們可以確定該直線與凸多邊形的交點個數和所有交點的座標(如果有的話)。

    現在,需要你寫一個程序,通過控制衛星發出的探測波來確定這個凸多邊形。

    【交互方法】

    本題是一道交互式題目,你的程序應當和測試庫進行交互,而不得訪問任何文件。測試庫提供3組函數,分別用於程序的初始化,與測試庫的交互,以及返回結果。它們的用法與作用如下:

  • prog_initialize必須先調用,但只能調用一次,用作初始化測試庫;

  • 測試庫提供兩個函數ask_x和ask_y作爲與測試庫交互的方式。其中ask_x(x0, y1, y2)的的作用是詢問直線x=x0和多邊形的交點,ask_y(y0, x1, x2)的作用是詢問直線y=y0與多邊形的交點,函數的返回值是交點的個數。ask_x(x0, y1, y2)調用後,y1和y2被賦值爲交點的y座標;ask_y(y0, x1, x2)調用後,x1和x2被賦值爲交點的x座標。如果只有一個交點,那麼x1和x2或y1和y2的值相同;如果沒有交點,那麼x1和x2或y1和y2的值 沒有意義。
  • 最後的一組函數是你的程序用來向測試庫返回結果的。這裏包括返回多邊形面積的ret_area(s),返回多邊形頂點數目的 ret_n(n),返回多邊形頂點座標的ret_vertex(x, y)。需要注意的事,這裏ret_area是必須先於ret_n調用的,而ret_n又是必須先於ret_vertex調用的。不合適的調用方式將會強制 你的程序非法退出。這裏你需要在調用ret_n後調用n次ret_vertex返回多邊形的頂點,但需要注意的是,如果你用ret_n返回的結果是錯誤 的,那麼測試庫將會馬上終止你的程序,並不接受下面的結果;同樣的,如果ret_vertex中返回了錯誤的結果,那麼測試庫也會馬上終止你的程序。如果 ret_vertex的結果均是正確的,那麼測試庫將會在你返回最後一個頂點座標後終止你的程序。
  • 注意:你需要按照逆時針順序返回所有頂點的座標,不過你可以從任意一個頂點開始。

    【對使用Pascal選手的提示】

    你的程序應當使用如下的語句引用測試庫。

    uses detect_lib;
    測試庫使用的函數原型爲:
    procedure prog_initialize;
      function ask_x(const x0: longint; var y1, y2: double): longint;
      function ask_y(const y0: longint; var x1, x2: double): longint;
      procedure ret_area(const s: double);
      procedure ret_n(const n: longint);
      procedure ret_vertex(const x, y:longint);
    【對使用C/C++選手的提示】

    你應當建立一個工程,把文件libdetect.o包含進來,然後在程序頭加上一行:

    #include “detect_lib.h”
    測試庫使用的函數原型爲:
    void prog_initialize();
      int ask_x(int x0, double y1, double y2);
      int ask_y(int y0, double x1, double x2);
      void ret_area(double s);
      void ret_n(int n);
      void ret_vertex(int x, int y);
    【數據說明】

    如果凸多邊形的座標如圖所示,那麼一種可能得滿分的調用方案如下:

    Image:Detect1.gif

    Pascal選手的調用方法

    C/C++選手的調用方法

    說明

    Prog_initialize;

    prog_initialize();

    初始化程序

    ask_x(-6, y1, y2);

    ask_x(-6, &y1, &y2);

    返回值1y1=2y2=2

    ask_x(-5, y1, y2);

    ask_x(-5, &y1, &y2);

    返回值2y1=3.4y2=-5

    ask_y(2, x1, x2);

    ask_y(2, &x1, &x2);

    返回值2x1=-6x2=16

    ask_y(-20, x1, x2)

    ask_y(-20, &x1, &x2)

    返回值0x1x2中的值無意義

    ret_area(241.5);

    ret_area(241.5);

    返回面積

    ret_n(5);

    ret_n(5);

    返回n

    ret_vertex(8, -9);

    ret_vertex(8, -9);

    返回頂點(8, -9)

    ret_vertex(16, 2);

    ret_vertex(16, 2);

    返回頂點(16, 2)

    ret_vertex(-1, 9);

    ret_vertex(-1, 9);

    返回頂點(-1, 9)

    ret_vertex(-6, 2);

    ret_vertex(-6, 2);

    返回頂點(-6, 2)

    ret_vertex(-5, -5);

    ret_vertex(-5, -5);

    返回頂點(-5, -5)

    注意,該例子只是對庫函數的使用說明,並沒有算法上的意義。

    這裏n最大爲200,x、y座標在[-10000, 10000]這個區間內。

    【評分方法】

    如果你的程序有下列情況之一,得0分:

  • 訪問了任何文件(包括臨時文件)或者自行終止;

  • 非法調用庫函數;
  • 讓測試庫異常退出。

    否則每個測試點你的得分按這樣來計算:包括頂點數提交正確的1分,面積提交正確的2分,頂點座標完全正確的2分,分數累計。剩下的5分將根據你調用ask_x和ask_y的總次數進行評判,公式如下:

    Image:Detect2.gif

    這裏x爲你的程序調用的ask_x和ask_y的次數,score爲你的得分。

    【你如何測試自己的程序】

  • 在工作目錄下建立一個文件叫做detect.in,文件的第一行包括一個整數n爲頂點的數目,以下n行每行兩個整數按照逆時針方向給出凸多邊形的頂點座標;

  • 執行你的程序,此時測試庫會產生輸出文件detect.log,該文件中包括了你程序和庫交互的記錄和最後的結果;
  • 如果程序正常結束,detect.log的最後一行會給出你的程序的分數;
  • 如果程序非法退出,則我們不保證detect.log中的內容有意義。

相關日誌