NOI 2003 卫星探测

This post is written in Chinese. Please consider using Google Translate

这道题我的方法是二分判断+计算几何。

首先要找到多边形的边界,可以用四个点分别表示多边形上下左右边界的一个顶点。寻找边界可以用二分的方法。由于已知原点一定在多边形内或边上,寻找左边界就可以从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中的内容有意义。

Related posts